QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#551930#9248. An Easy Math Problemucup-team3670#TL 0ms3860kbC++171.2kb2024-09-07 19:11:022024-09-07 19:11:02

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-07 19:11:02]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 3860kb
  • [2024-09-07 19:11:02]
  • Submitted

answer

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)

using namespace std;

long long n;
vector<pair<long long, long long>> res;

void brute(int i, const vector<pair<long long, int>> &f, long long pq, long long q){
	if (i == int(f.size())){
		long long p = pq / q;
		if (p > q) return;
		long long g = __gcd(p, q);
		res.push_back({p / g, q / g});
		return;
	}
	for (int j = 0; j <= f[i].second; ++j){
		long long nq = q;
		for (int k = 0; k <= j; ++k){
			brute(i + 1, f, pq, nq);
			nq *= f[i].first;
		}
		pq *= f[i].first;
	}
}

void solve(){
	vector<pair<long long, int>> f;
	for (long long i = 2; i * i <= n; ++i) if (n % i == 0){
		int cnt = 0;
		while (n % i == 0){
			++cnt;
			n /= i;
		}
		f.push_back({i, cnt});
	}
	if (n > 1){
		f.push_back({n, 1});
	}
	res.clear();
	brute(0, f, 1, 1);
	sort(res.begin(), res.end());
	res.resize(unique(res.begin(), res.end()) - res.begin());
	cout << res.size() << '\n';
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int tc;
	cin >> tc;
	while (tc--){
		cin >> n;
		solve();
	}
}

详细

Test #1:

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

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: