QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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;
}
詳細信息
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'