QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #211506 | #4624. Shortest Path in GCD Graph | yiyiyi# | AC ✓ | 1773ms | 87036kb | C++14 | 1.1kb | 2023-10-12 17:30:15 | 2023-10-12 17:30:16 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 10202000
using namespace std;
const int mo=998244353;
inline int read(){
int x=0,w=0;char ch=getchar();
while (!isdigit(ch))w|=ch=='-',ch=getchar();
while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return w?-x:x;
}
int mn[N],pre[N],tot,f[N],a[1002];
signed main(){
int n=read(),Q=read();
mn[1]=1;
for (int i=2;i<=n;++i){
if (!f[i])mn[pre[++tot]=i]=i;
for (int j=1;j<=tot&&pre[j]*i<=n;++j){
f[i*pre[j]]=1;
if (i%pre[j])
mn[i*pre[j]]=min(mn[i],pre[j]);
else{
mn[i*pre[j]]=mn[i];
break;
}
}
}
while (Q--){
int u=read(),v=read(),uu=u,vv=v;
if (__gcd(u,v)==1){puts("1 1");continue;}
printf("2 ");
int ans=0,tot=0;
for (;u>1;u/=mn[u])a[++tot]=mn[u];
for (;v>1;v/=mn[v])a[++tot]=mn[v];
sort(a+1,a+1+tot);
tot=unique(a+1,a+1+tot)-a-1;
for (int s=0;s<(1<<tot);++s){
int cnt=0,t=n;
for (int i=1;i<=tot;++i)
if (s&(1<<i-1))
++cnt,t/=a[i];
(ans+=(cnt&1?-1:1)*t)%=mo;
}
printf("%d\n",(ans+(__gcd(uu,vv)==2)+mo)%mo);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1773ms
memory: 87036kb
input:
10000000 50000 6063825 1688077 9748275 1717197 5067284 9994733 8895125 6988260 9446181 5378152 9460161 1794337 3393611 9297610 7525386 5806968 9608609 2225468 9808741 2596273 606784 8423027 2361246 4662937 4385583 1195254 8440346 4819524 4256844 679638 8959165 3868431 9063859 4480534 9568261 1389414...
output:
1 1 2 5240548 1 1 2 2666605 1 1 1 1 1 1 2 2903766 1 1 1 1 1 1 1 1 2 3216618 2 3333325 2 3311989 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2637091 1 1 1 1 1 1 2 3589273 1 1 2 2178004 1 1 1 1 1 1 2 3075313 2 4571237 2 3392155 2 3999993 1 1 2 3144296 1 1 1 1 2 2840582 1 1 2 5121187 2 2461856 1 1 1 1 1 1 1 1 1 ...
result:
ok 50000 lines