QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#576521 | #9248. An Easy Math Problem | rxzfn639 | WA | 3ms | 3884kb | C++23 | 2.7kb | 2024-09-19 20:48:11 | 2024-09-19 20:48:11 |
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-19 20:48:11]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 P = 998244353;
i64 mul(i64 a, i64 b, i64 m) {
return static_cast<__int128>(a) * b % m;
}
i64 power(i64 a, i64 b, i64 m) {
i64 res = 1 % m;
for (; b; b >>= 1, a = mul(a, a, m))
if (b & 1)
res = mul(res, a, m);
return res;
}
bool isprime(i64 n) { // Miller-Rabin
if (n < 2) return false;
static constexpr int B[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
for (int p : B) {
if (n == p) return true;
if (n % p == 0) return false;
}
i64 m = (n - 1) >> __builtin_ctz(n - 1);
for (int p : B) {
i64 t = m, a = power(p, m, n);
while (t != n - 1 && a != 1 && a != n - 1) {
a = mul(a, a, n);
t *= 2;
}
if (a != n - 1 && t % 2 == 0) return false;
}
return true;
}
vector<i64> factorize(i64 n) { // Pollard-Rho
vector<i64> p;
function<void(i64)> f = [&](i64 n) {
if (n <= 10000) {
for (int i = 2; i * i <= n; i++)
for ( ; n % i == 0; n /= i)
p.push_back(i);
if (n > 1)
p.push_back(n);
return;
}
if (isprime(n)) {
p.push_back(n);
return;
}
auto g = [&](i64 x) {
return (mul(x, x, n) + 1) % n;
};
i64 x0 = 2;
while (true) {
i64 x = x0, y = x0;
i64 d = 1, pow = 1, lam = 0, v = 1;
while (d == 1) {
y = g(y);
++lam;
v = mul(v, abs(x - y), n);
if (lam % 127 == 0) {
d = gcd(v, n);
v = 1;
}
if (pow == lam) {
x = y;
pow *= 2;
lam = 0;
d = gcd(v, n);
v = 1;
}
}
if (d != n) {
f(d);
f(n / d);
return;
}
++x0;
}
};
f(n);
sort(p.begin(), p.end());
return p;
}
void solve() {
i64 n;
cin >> n;
auto p = factorize(n);
int cnt = 0, ans = 1, siz = 0;
for (int i = 0; i < p.size(); i++) {
cnt++;
if (i == p.size() || p[i] != p[i + 1]) {
siz++;
ans *= (cnt + 1);
cnt = 0;
}
}
if (siz > 1) ans++;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3672kb
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
Wrong Answer
time: 3ms
memory: 3884kb
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:
1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 1025 ...
result:
wrong answer 1st lines differ - expected: '29525', found: '1025'