QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#551930 | #9248. An Easy Math Problem | ucup-team3670# | TL | 0ms | 3860kb | C++17 | 1.2kb | 2024-09-07 19:11:02 | 2024-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]
- 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...