题目：CF986F Oppa Funcan Style Remastered
一道神仙题，Div1的F。。
大概是目前我做过的码量较大细节较多的题之一了。（可能我比较菜）
这里写一下心得。
首先我们知道k=1肯定不行，因为没有质因子。
然后如果k是个质数我们只要判断整除就可以了。
如果k有两个质因子，我们就跑一下exgcd，判断是否有非负整数解。
如果k有三个及以上质因子，可以证明k的最小质因子不超过10^5，于是愉快地跑同余最短路。
由于常数比较大加了不少黑科技优化。
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #include<algorithm>
5 #define it register int
6 #define rll register long long
7 #define il inline
8 using namespace std;
9 typedef long long ll;
10 typedef unsigned long long ull;
11 typedef long double ldb;
12 const int N=2000005;
13 const ll inf=4557430888798830399ll;
14 const int M=(1<<19)-1;
15 const int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
16 int T,top1,top2,cnt;
17 ll d[N],pr[N],q[N];
18 bool inq[N],o[N];
19 struct ky{
20 ll n,k,id;
21 bool operator<(const ky&p)const{
22 return k^p.k?k<p.k:n<p.n;
23 }
24 }Q[N];
25 il void exgcd(ll a,ll b,ll&x,ll &y,ll &d){
26 if(!b){d=a,x=1,y=0;return;}
27 exgcd(b,a%b,y,x,d),y-=a/b*x;
28 }
29 namespace SPFA{
30 il void spfa(){
31 memset(d,0x3f,sizeof(d)),memset(inq,0,sizeof(inq)),d[0]=0,top1=0,top2=1,q[1]=0;rll fir=pr[1],x;
32 while(top1!=top2){
33 rll top=q[(++top1)&M];
34 for(it i=2;i<=cnt;++i)
35 if(d[x=(top+pr[i])%fir]>d[top]+pr[i]){
36 d[x]=d[top]+pr[i];
37 if(!inq[x]) inq[x]=1,q[(++top2)&M]=x;
38 }
39 inq[top]=false;
40 }
41 }
42 il void Test(rll n,bool &ans){ans=(d[n%pr[1]]<=n);}
43 }
44 using SPFA :: Test;
45 using SPFA :: spfa;
46 //同余最短路
47 namespace PR{
48 il ll mul(rll a,rll b,rll p){return (a*b-(ull)((ldb)a/p*b+1e-7)*p+p)%p;}
49 il ll mo(rll a,rll b,rll p){return a+b>=p?a+b-p:a+b;}
50 il ll sub(rll a,rll b,rll p){return a<b?a-b+p:a-b;}
51 il void ksm(rll a,rll b,rll p,ll &now){
52 now=1;
53 while(b){
54 if(b&1) now=mul(now,a,p);
55 b>>=1,a=mul(a,a,p);
56 }
57 }
58 il bool isp(rll num){
59 for(it i=0;i<15;++i) if(!(num%p[i])) return num==p[i];
60 rll r=num-1;it pw=0;
61 while(!(r&1)) ++pw,r>>=1;
62 for(it i=0;i<15;++i){
63 rll y,x;ksm(p[i],r,num,x);
64 for(it j=1;j<=pw&&x>1;++j){
65 y=mul(x,x,num);
66 if(y==1&&x!=num-1) return 0;
67 x=y;
68 }
69 if(x!=1) return 0;
70 }
71 return 1;
72 }
73 il void gcd(rll a,rll b,ll &d){
74 if(!b){d=a;return;}
75 gcd(b,a%b,d);
76 }
77 il ll div(rll n,it B,it a){
78 if(!(n&1)) return 2;
79 rll cntx,cnty,x=2,y=2,d=1;
80 while(1){
81 cntx=x,cnty=y;
82 for(it i=1;i<=B;++i)
83 x=mo(mul(x,x,n),a,n),y=mo(mul(y,y,n),a,n),y=mo(mul(y,y,n),a,n),d=mul(sub(x,y,n),d,n);
84 gcd(n,d,d);
85 if(d==1) continue;
86 if(d!=n) return d;
87 x=cntx,y=cnty;
88 for(it i=1;i<=B;++i){
89 x=mo(mul(x,x,n),a,n),y=mo(mul(y,y,n),a,n),y=mo(mul(y,y,n),a,n),gcd(sub(x,y,n),n,d);
90 if(d!=1) return d%n;
91 }
92 return 0;
93 }
94 }
95 il void rho(ll n){
96 if(n==1) return;
97 if(isp(n)){pr[++cnt]=n;return;}
98 it B=pow(n,0.125),a=1;
99 rll d=div(n,B,a);
100 while(!d) ++a,d=div(n,B,a);
101 rho(n/d),rho(d);
102 }
103 il void test(rll n){cnt=0,rho(n),sort(pr+1,pr+1+cnt);}
104 }
105 using PR :: test;
106 using PR :: isp;
107 using PR :: mul;
108 //快速分解质数
109 namespace io {
110 const int SIZE = (1 << 21) + 1;
111 char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
112 int f, qr;
113 #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
114 inline void flush () {fwrite (obuf, 1, oS - obuf, stdout);oS = obuf;}
115 template <class I>
116 inline void fr (I &x) {
117 for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
118 for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
119 x *= f;
120 }
121 struct Flusher_ {~Flusher_() {flush();}} io_flusher_;
122 }
123 using io :: fr;
124 int main(){
125 fr(T);
126 for(it i=1;i<=T;++i) fr(Q[i].n),fr(Q[i].k),Q[i].id=i;
127 sort(Q+1,Q+1+T);//不同的k不超过50个，把k相同的放在一起处理
128 for(it i=1,j=1;i<=T;i=j){
129 if(Q[i].k==1){for(j=i;Q[j].k==Q[i].k&&j<=T;++j);continue;}
130 test(Q[i].k);
131 if(cnt==1) for(j=i;Q[j].k==Q[i].k&&j<=T;++j) o[Q[j].id]=(Q[j].n%pr[1]?0:1);
132 else if(cnt==2){
133 rll x,y,d;exgcd(pr[1],pr[2],x,y,d);
134 x=(x%pr[2]+pr[2])%pr[2];
135 for(j=i;Q[j].k==Q[i].k&&j<=T;++j){
136 if(Q[j].n%d){o[Q[j].id]=0;continue;}
137 rll tx=mul(x,Q[j].n,pr[2]),ty=Q[j].n-tx*pr[1]; //exgcd计算非负整数解
138 o[Q[j].id]=(ty>=0);
139 }
140 }
141 else if(cnt>2){spfa();for(j=i;Q[j].k==Q[i].k&&j<=T;++j) Test(Q[j].n,o[Q[j].id]);}
142 }
143 for(it i=1;i<=T;++i) o[i]?puts("YES"):puts("NO");
144 return 0;
145 }
146 //namespace封装黑科技优化（快好几倍）