一、题目
二、解法
话说很多题都想了同余最短路，今天终于用上一回了。
首先可以暴力预处理 \(\sqrt k\) 以内的质因数然后对 \(k\) 搞质因数分解，其它因数可以被质数之和表示所以没用。
然后跑同余最短路即可，时间复杂度是 \(O(\)最小质因数\(\cdot\log)\)，我们可以通过讨论来降低复杂度。如果质因数个数 \(=1\) 直接判断是否为倍数，\(=2\) 相当于判断二元一次方程有无解，否则最小值因数 \(\leq \sqrt[3]{k}\)
那么时间复杂度 \(O(50\cdot \sqrt[3]k\cdot \log+\sqrt k)\)
三、总结
同余最短路的模型就是无限选若干个数，问能不能凑出某个数\(/\)某个数以内能凑出数的个数。
如果复杂度和定和\(/\)定乘积的量有关，可以通过小范围讨论来大幅降低复杂度。
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
const int M = 33000005;
const int N = 100005;
bool vis[M];int cnt,p[M];
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int m,k,dis[N],a[N],ans[N],in[N];
struct node{int n,id;};map<int,vector<node>> mp;
void init(int n)
{
for(int i=2;i<=n;i++)
{
if(!vis[i]) p[++cnt]=i;
for(int j=1;j<=cnt && i*p[j]<=n;j++)
{
vis[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
}
void dec(int n)
{
k=0;
for(int i=1;i<=cnt && p[i]*p[i]<=n;i++)
if(n%p[i]==0)
{
a[++k]=p[i];
while(n%p[i]==0) n/=p[i];
}
if(n>1) a[++k]=n;
}
int qkpow(int a,int b,int m)
{
int r=1;a%=m;
while(b>0)
{
if(b&1) r=r*a%m;
a=a*a%m;
b>>=1;
}
return r;
}
void work(int x,vector<node>&v)
{
dec(x);
if(x==1) return ;
if(k==1)
{
for(auto t:v)
ans[t.id]=t.n%a[k]?0:1;
return ;
}
if(k==2)
{
for(auto t:v)
{
int k=t.n%a[1]*qkpow(a[2],a[1]-2,a[1])%a[1];
ans[t.id]=k*a[2]<=t.n;
}
return ;
}
queue<int> q;
memset(dis,0x3f,sizeof dis);
dis[0]=0;q.push(0);in[0]=1;
while(!q.empty())
{
int u=q.front();q.pop();
in[u]=0;
for(int i=2;i<=k;i++)
{
int v=(u+a[i])%a[1];
if(dis[v]>dis[u]+a[i])
{
dis[v]=dis[u]+a[i];
if(!in[v]) q.push(v),in[v]=1;
}
}
}
for(auto t:v)
ans[t.id]=dis[t.n%a[1]]<=t.n;
}
signed main()
{
m=read();init(33000000);
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
mp[y].push_back(node{x,i});
}
for(auto tmp:mp) work(tmp.first,tmp.second);
for(int i=1;i<=m;i++)
puts(ans[i]?"YES":"NO");
}