QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556710 | #9248. An Easy Math Problem | zzm666 | TL | 0ms | 3572kb | C++14 | 3.1kb | 2024-09-10 20:19:46 | 2024-09-10 20:19:47 |
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:19:46]
- 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 = 0;
while (b) {
if (b & 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
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 = 16;//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: 3572kb
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...