寻梦 （HG 2018.8.13 T3）

  这道题真的是太妙了。。。可以说暴力都有一定的思维难度。。。 首先我们要知道，这n个城市肯定要被分为若干个环，而且这些环的长度要是k的质因数，这样才能在第k天的时候刚好回来。所以问题就变成了，用k的所有质因数，去凑成n。 然后，暴力大法师，暴力背包就来了。。。 震惊！~~历史~~数论~~难~~题正解竟要用dijstra/spfa求最短路！！ 盯一下数据范围，我们震惊地发现，k不同的只有50个！所以我们完全可以把做过的k存下来，后面碰到相同的k直接调用即可。 然后，我们一顿乱搞，先把k的质因数处理出来了。 然后，我们震惊地（大雾）发现，原来，这若干个只质因数，肯定是由若干个最小的质因数和若干个其他质因数组成的！然后我们就可以得到，n%p1(最小质因数)=(a2p2+a3p3+a4p4+……+anpn)%p1,震惊！！！（大雾） 额，为什么选p1呢。。因为。。。p1最小。。。数组开的下。。题目里有p1的数据范围orz。。（截图没截进去，最小的质因数小于10^5) 然后！！！ 我们引入神奇的dijstra。用dis[now][i]存，now的除最小质因数的质因数中，膜p1为i的最小和。什么意思，就是你要让一坨数的和尽量小，并且和膜p1的余数为i。然后，dis[now][n%p1]就是，若干个p2~pn的余数为n%p1的最小和。然后，如果最后的dis[now][n%p1]>n,说明肯定不存在了，如果<=n，你可以用若干个p1来填补 那么now的那一维有什么用呢。。没错，就是存一下。。以方便日后提取。。 然后转移（spfa） ```cpp int v=(u+pi)%p1 if(dis[now][v]>dis[now][u]+pi) dis[now][v]=dis[now][u]+pi; blablabla~ ``` dijstra见下方代码。。 代码： ```cpp #include<map> #include<set> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; long long read() { long long x=0,flag=0; char ch=getchar(); if(ch=='-') flag=1; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar(); if(flag) return -x; return x; } const long long N=(long long)sqrt(1e15); long long n,k,cnt=0,tot=0; long long rec[100100]; long long prim[100010]; long long f[N],l[60]; long long num[60][1000]; long long dis[60][100100]; struct yzf { long long d,re; bool operator < (const yzf b) const {return d>b.d;} }; void exgcd(long long a,long long b,long long &x,long long &y) { if(b==0) { x=1,y=0; return; } long long q=a/b,r=a%b; exgcd(b,r,y,x); y-=q*x; } int main() { int tmp=read(),T=read(); for(int i=2;i<N;i++) { if(f[i]==0) prim[++tot]=f[i]=i; for (int j=1;j<=tot && prim[j]<=f[i]; j++) { int tmp=prim[j]*i; if(tmp>=N) break; f[tmp]=prim[j]; } } while(T--) { n=read(),k=read(); int p=0; for(int i=1;i<=cnt;i++) if(rec[i]==k) p=i; if(!p) { p=++cnt,rec[cnt]=k; long long tmp=k; for(int i=1;prim[i]*prim[i]<=tmp;i++) { if(tmp%prim[i]==0) { num[p][++l[p]]=prim[i]; while(tmp%prim[i]==0) tmp/=prim[i]; } } if(tmp!=1) num[p][++l[p]]=tmp; if(l[p]>2) { memset(dis[p],0x7f,sizeof(dis[p])); static priority_queue <yzf> h; dis[p][0]=0;h.push((yzf){0,0}); while(!h.empty()) { yzf u=h.top();h.pop(); for(int i=2;i<=l[p];i++) { int v=(u.re+num[p][i])%num[p][1]; if(dis[p][v]>u.d+num[p][i]) { dis[p][v]=u.d+num[p][i]; h.push((yzf){dis[p][v],v}); } } } } } bool flag=0; for(int i=1;i<=l[p];i++) if(n%num[p][i]==0) { printf("YES\n"); flag=1; break; } if(flag) continue; if(l[p]<=1) { printf("NO\n"); continue; } if(l[p]==2) { long long x = 0, y = 0; exgcd(num[p][1],num[p][2],x,y); y=(y%num[p][1]+num[p][1])%num[p][1]; long long tmp=y*(n%num[p][1])%num[p][1]*num[p][2]; if(tmp<=n) printf("YES\n"); else printf("NO\n"); continue; } int tmp=n%num[p][1]; if(dis[p][tmp]<=n) printf("YES\n"); else printf("NO\n"); } return 0; } ```