QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#658024 | #9248. An Easy Math Problem | Vegetog# | AC ✓ | 176ms | 3936kb | C++20 | 4.1kb | 2024-10-19 16:00:20 | 2024-10-31 22:08:50 |
Judging History
你现在查看的是测评时间为 2024-10-31 22:08:50 的历史记录
- [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-10-19 16:00:20]
- 提交
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll =long long;
const int N=2e5+6;
namespace prime_fac {
const int S = 8; // 随机算法判定次数,8~10 就够了
// 龟速乘
long long mult_mod(long long a, long long b, long long c) {
a %= c, b %= c;
long long ret = 0;
long long tmp = a;
while (b) {
if (b & 1) {
ret += tmp;
if (ret > c) ret -= c;
}
tmp <<= 1;
if (tmp > c) tmp -= c;
b >>= 1;
}
return ret;
}
// 快速幂
long long qow_mod(long long a, long long n, long long _mod) {
long long ret = 1;
long long temp = a % _mod;
while (n) {
if (n & 1) ret = mult_mod(ret, temp, _mod);
temp = mult_mod(temp, temp, _mod);
n >>= 1;
}
return ret;
}
// 是合数返回true,不一定是合数返回false
bool check(long long a, long long n, long long x, long long t) {
long long ret = qow_mod(a, x, n);
long long last = ret;
for (int i = 1; i <= t; i++) {
ret = mult_mod(ret, ret, n);
if (ret == 1 && last != 1 && last != n - 1) return true;
last = ret;
}
if (ret != 1) return true;
return false;
}
// 是素数返回true,不是返回false
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
bool Miller_Rabin(long long n) {
if (n < 2) return false;
if (n == 2) return true;
if ((n & 1) == 0) return false;
long long x = n - 1;
long long t = 0;
while ((x & 1) == 0) { x >>= 1; t++; }
for (int i = 0; i < S; i++) {
long long a = rng() % (n - 1) + 1;
if (check(a, n, x, t))
return false;
}
return true;
}
long long factor[100];// 存质因数
int tol; // 质因数的个数,0~tol-1
long long gcd(long long a, long long b) {
long long t;
while (b) {
t = a;
a = b;
b = t % b;
}
if (a >= 0) return a;
return -a;
}
long long pollard_rho(long long x, long long c) {
long long i = 1, k = 2;
long long x0 = rng() % (x - 1) + 1;
long long y = x0;
while (1) {
i++;
x0 = (mult_mod(x0, x0, x) + c) % x;
long long d = gcd(y - x0, x);
if (d != 1 && d != x) return d;
if (y == x0) return x;
if (i == k) { y = x0; k += k; }
}
}
// 对n质因数分解,存入factor,k一般设置为107左右
void findfac(long long n, int k) {
if (n == 1) return;
if (Miller_Rabin(n)) {
factor[tol++] = n;
return;
}
long long p = n;
int c = k;
while (p >= n) p = pollard_rho(p, c--);
findfac(p, k);
findfac(n / p, k);
}
vector<int> fac(long long n) {
tol = 0;
vector<int>ret;
findfac(n, 107);
for (int i = 0; i < tol; i++)ret.push_back(factor[i]);
return ret;
}
}
int b[20];
void solve()
{
ll n,m=0,x;
cin>>n;
vector<int> fac = prime_fac::fac(n);
vector<ll> a;
unordered_map<ll, ll> mp;
for(auto i : fac) {
if(mp[i] == 0)
a.push_back(i);
mp[i] ++ ;
}
ll ans = 1, res = 0;
int cp=pow(2,(a.size()));
for(int i=1;i<cp;i++){
int er=i,w=0;
while(er){
if(er%2){
b[++w]=1;
}else b[++w]=0;
er/=2;
}
res=1;
for(int j=1;j<=w;j++){
if(b[j]==0)continue;
res*=mp[a[j-1]]*2;
}
res/=2;
ans+=res;
}
cout << ans << "\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr),cout.tie(nullptr);
int T=1;
cin>>T;
while(T--){
solve();
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3784kb
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: 176ms
memory: 3936kb
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: 0
Accepted
time: 84ms
memory: 3932kb
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...
output:
14 5 2 5 23 95 68 14 8 68 203 14 23 32 38 41 8 8 14 2 608 41 158 338 23 41 14 5 14 41 14 203 41 14 17 446 5 53 59 878 2 14 365 203 14 203 2 122 32 95 41 41 5 23 14 41 5 5 14 122 23 203 608 23 41 122 2 14 95 2 68 41 203 14 230 41 68 23 50 14 32 14 8 5 5 5 68 68 122 293 473 5 41 41 14 2 14 14 5 2 122 ...
result:
ok 2000 lines
Extra Test:
score: 0
Extra Test Passed