QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#556110#9248. An Easy Math ProblemSLF666#TL 0ms3568kbC++201.0kb2024-09-10 15:06:562024-09-10 15:06:57

Judging History

This is the latest submission verdict.

  • [2024-10-31 22:36:43]
  • hack成功,自动添加数据
  • (/hack/1098)
  • [2024-10-31 22:13:58]
  • hack成功,自动添加数据
  • (/hack/1096)
  • [2024-10-31 22:00:43]
  • hack成功,自动添加数据
  • (/hack/1095)
  • [2024-09-10 15:06:57]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 3568kb
  • [2024-09-10 15:06:56]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ll long long
map<pair<ll,ll>,int> mp;
set<ll> st;
ll n;
void solve(){
	cin >> n;
	ll nn = n;
	mp.clear();
	st.clear();
	ll i;
	vector<ll> a;
	for(i = 2 ; i <= n ; i ++) {
		while(n != i) {
			if(n % i == 0) {
				a.push_back(i);
				n /= i;
			}
			else break;
		}
	}
	if(n > 1) a.push_back(n);
	a.push_back(1);
	for(i = 0 ; i < a.size() ; i ++) {
		set<ll> st2;
		st2 = st;
		for(auto &it : st2) {
			st.insert(it * a[i]);
		}
		st.insert(a[i]);
	}
//	for(auto &it:st) cout << it << ' ';
//	cout << endl;
	for(auto &xx:st){
		for(auto &yy:st){
		    ll x = xx,  y = yy;
		    if(nn % (x * y) == 0){
		    	if(x > y)swap(x , y);
		    	ll tmp = __gcd(x , y);
		    	x /= tmp , y /= tmp;
		    	mp[{x, y}] = 1;
			}
		}
	}
	cout << mp.size() << endl;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t = 1;
	cin>>t;
	for(int i=1;i<=t;i++){
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3568kb

input:

10
1
2
3
4
5
6
7
8
9
10

output:

1
2
2
3
2
5
2
4
3
5

result:

ok 10 lines

Test #2:

score: -100
Time Limit Exceeded

input:

2000
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
646969323...

output:


result: