QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556706 | #9248. An Easy Math Problem | zzm666 | TL | 813ms | 3596kb | C++14 | 3.0kb | 2024-09-10 20:17:48 | 2024-09-10 20:17:48 |
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 20:17:48]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define ld long double
vector<ll> a;
set<ll> st;
long long multi(long long a, long long b, long long p) {
long long res = a * b % p;
return res;
}
long long qpow(long long a, long long b, long long p) {
long long res = 1;
while (b) {
if (b & 1) res = multi(res, a, p);
a = multi(a, a, p);
b >>= 1;
}
return res;
}
int test_time = 18;//1/4的概率误判, 最好8次以上
bool miller_rabin(long long n) {//test_time * logn判断是否为素数 记得加上面的龟速乘和快速幂
if (n < 3 || n % 2 == 0) return n == 2;
long long b = n - 1, k = 0, j;
while (b % 2 == 1) b /= 2, ++k;
for (int i = 0; i < test_time; ++i) {
long long a = qpow(rand() % (n - 2) + 2, b, n);
if (a == 1) continue;
for (j = 0; j < k; ++j) {
if (a != n - 1) break;
a = multi(a, a, n);
}
if (j == k) return 0;
}
return 1;
}
long long f(long long x, long long c, long long p) { return (multi(x, x, p) + c) % p; }
long long pollard_rho(long long N, long long c) {//启发式分解质因数, 单次操作找到一个质因子 记得加上面的函数或手敲
long long xi = rand() % (N - 1) + 1, xj = f(xi, c, N);
while (xi != xj) {
long long d = __gcd(xi - xj, N);
if (d > 1) return d;
xj = f(f(xj, c, N), c, N);
xi = f(xi, c, N);
}
return N;
}
void factor(long long N, std::map<long long, int> &factors) {//启发式分解质因数找到所有质因子,记得加函数
if (miller_rabin(N)) ++factors[N];
else {
long long c = rand() % (N - 1) + 1;
long long d = N;
while (d >= N)
d = pollard_rho(N, c--);
factor(N / d, factors);
factor(d, factors);
}
}
void solve(){
ll n, nn;
cin >> n;
// n = 6469693230ll;
// n = 479001600ll * 13;
nn = n;
ll i;
map<ll, int> mp;
st.clear();
a.clear();
if(n != 1) factor(nn, mp);
for(i = 1 ; i * i <= n ; i ++) {
if(n % i == 0) {
a.push_back(i);
a.push_back(n / i);
// cout << i << ' ';
// st.insert(i);
// st.insert(n / i);
}
// cout << i << ' ';
}
for(i = 0 ; i < a.size() ; i ++) {
st.insert(a[i]);
// if(a[i] != st[st.size() - 1] || st.size() == 0) st.push_back(a[i]);
}
st.erase(1);
ll ans = 0;
for(auto &it1:st) {
ll sum = 1;
for(auto &it2:mp) {
if(it1 % it2.first == 0) continue;
sum *= (it2.second + 1);
}
ans += sum - 1;
// cout << sum - 1 << ' ';
}
ans /= 2;
// cout << "ans = " << ans << ' ';
ll sum = 1;
for(auto &it:mp) {
sum *= (it.second + 1);
// ans += (it.second + 1);
// cout << it.first << ' ' << it.second << endl;
}
cout << ans + sum << 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: 3544kb
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: 0
Accepted
time: 813ms
memory: 3596kb
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:
29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 ...
result:
ok 2000 lines
Test #3:
score: -100
Time Limit Exceeded
input:
2000 1763047095 79735483 1016286871 2864801397 2327774116 2668010360 3469893354 3634459021 1613699068 781737219 574741575 2763134701 1458502604 1822260248 2281150332 2924219311 2493931196 3735904708 158802001 2006921221 729928782 1974841034 727412600 2873393292 1291087179 2741607663 1893408215 29827...