QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#577240 | #6890. Guess | changziliang | AC ✓ | 933ms | 3928kb | C++14 | 3.3kb | 2024-09-20 09:33:39 | 2024-09-20 09:33:39 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long LL;
const LL Mod = 998244353;
typedef __int128 BIG;
vector< LL > pp, p;
vector< LL > C;
inline LL mul(LL a,LL b,LL mod){return (BIG)a*b%mod;}
LL Pow(LL a,LL b,LL mod)
{
LL res=1;
while(b)
{
if(b&1)res=mul(res,a,mod);
a=mul(a,a,mod);
b>>=1;
}
return res;
}
mt19937 rnd(time(0));
LL Make(LL l,LL r){return rand()%(r-l+1)+l;}
bool Miller_Rabin(LL n)
{
if(n<=3)return n!=1;
LL r=(n-1),c=0;
while(r%2==0)r/=2,c++;
for(int t=1;t<=3;t++)
{
LL a=Make(2,n-1);
LL x=a,y=Pow(a,r,n);
for(int i=1;i<=c;i++)
{
x=mul(y,y,n);
if(x==1&&y!=1&&y!=n-1)return 0;
y=x;
}
if(y!=1)return 0;
}
return 1;
}
LL c,mod;
LL f(LL x)
{
return (mul(x,x,mod)+c)%mod;
}
LL gcd(LL a,LL b)
{
if(!b)return a;
return gcd(b,a%b);
}
LL Pollard_Rho(LL n)
{
if(n%2==0)return 2ll;
c=Make(2,n-1);mod=n;
LL a=Make(2,n-1),b=1;
for(int i=1;;i<<=1)
{
a=b;
LL res=1;
for(int j=1;j<=i;j++)
{
b=f(b);
res=mul(res,abs(a-b),mod);
if(j%127==0)
{
LL d=gcd(res,n);
if(d>1)return d;
}
}
LL d=gcd(res,n);
if(d>1)return d;
}
return Pollard_Rho(n);
}
void resolve(LL n)
{
if(n==1)return;
if(Miller_Rabin(n))
{
// cout << "lll" << n << endl;
pp.pb(n);
return;
}
LL x=Pollard_Rho(n);
while(n%x==0)n/=x;
resolve(x);
resolve(n);
}
LL res;
bool vis[100];
LL Power(LL x, LL y) {
LL res = 1LL, k = x % Mod;
// cout << "RRR" << x << ' ' << y << endl;
while(y) {
if(y & 1) res = res * k % Mod;
y >>= 1;
k = k * k % Mod;
}
return res;
}
LL tims;
void get(int len) {
LL tmp = 1LL; int o = 0;
LL ct = 0;
for(int i = 0; i < len; i ++ ) {
// cout << "III" << ' ' << i << ' ' << p[i] << ' ' << C[i] << endl;
if(p[i] == Mod) {
if(!vis[i]) ct += C[i];
else ct += C[i] - 1LL, o ++;
continue;
}
if(!vis[i]) {
// cout << "YYY" << i << ' ' << p[i] << ' ' << C[i] << endl;
tmp = tmp * Power(1LL * p[i], 1LL * C[i]) % Mod;
// exit(0);
}
else {
// cout << "LLL" << i << endl;
tmp = tmp * Power(1LL * p[i], 1LL * C[i] - 1LL) % Mod;
o ++;
}
}
// cout << "GGGH" << tmp << ' ' << ct << endl;
// if(tmp % Mod == 0) {
// while(tmp % Mod == 0 && tmp) ct ++, tmp /= Mod;
// }
// cout << tmp << endl;
if(o & 1) tmp = Power(tmp, Mod - 2LL), ct = -ct;
if(tmp) res = res * tmp % Mod;
tims += ct;
}
void dfs(int x, int et) {
if(x == et) {
get(et);
return ;
}
vis[x] = 0;
dfs(x + 1, et);
vis[x] = 1;
dfs(x + 1, et);
}
void solve(LL n) {
pp.clear(); p.clear(); C.clear(); res = 1LL;
tims = 0;
resolve(n);
sort(pp.begin(), pp.end());
for(int i = 0; i < pp.size(); i ++ ) {
if(i == 0 || pp[i] != pp[i - 1]) p.pb(pp[i]);
}
for(int i = 0; i < p.size(); i ++ ) {
LL tmp = n; LL cnt = 0;
while(tmp % p[i] == 0 && tmp) {
cnt ++; tmp /= p[i];
}
C.pb(cnt);
}
// for(int i = 0; i < p.size(); i ++ ) {
// cout << "OOO" << p[i] << ' ' << C[i] << endl;
// }
int sz = p.size();
// cout << "UUUU" << sz << endl;
dfs(0, sz);
// cout << tims << endl;
if(tims != 0) printf("0 ");
else printf("%lld ", res);
}
int T;
int main()
{
// resolve(1532812);
scanf("%d", &T);
while(T -- ) {
LL n; scanf("%lld", &n);
solve(n);
}
return 0;
}
/*
998244353
3
1 2 3
1
26952597531
*/
詳細信息
Test #1:
score: 100
Accepted
time: 933ms
memory: 3928kb
input:
2000 19491001 1 998244353 26952597531 861547697451441000 996491788296388609 981763655235363000 1024000007168 996491787298144256 973929762490885200 891042123129958800 878912224686896400 804111184288011600 766710664088569200 930867627131442000 996491787298144256 812033461965726000 964953451315854000 8...
output:
19491001 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
ok single line: '19491001 1 0 1 1 0 1 1 1 1 1 1...6159 899999557 1 716046715 1 1 '