2020-2021:teams:legal_string:jxm2001:同余最短路
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:同余最短路 [2021/09/04 19:55] jxm2001 |
2020-2021:teams:legal_string:jxm2001:同余最短路 [2021/09/05 08:46] (当前版本) jxm2001 [例题三] |
||
|---|---|---|---|
| 行 163: | 行 163: | ||
| 预处理 $O(\sqrt k)$ 范围的数后对每个 $k$ 进行因式分解，时间复杂度 $O\left(\frac {\sqrt k}{\ln k}\right)$。 | 预处理 $O(\sqrt k)$ 范围的数后对每个 $k$ 进行因式分解，时间复杂度 $O\left(\frac {\sqrt k}{\ln k}\right)$。 | ||
| - | 如果 $k$ 是质数，只需要判定 $k\mid n$ 是否成立。如果 $k$ 有两种素因子，记为 $a,b$，于是等价于求解 $ax+by=n$ 的非负整数解。 | + | 如果 $k=1$，显然无解。如果 $k$ 是质数，只需要判定 $k\mid n$ 是否成立。 |
| + | |||
| + | 如果 $k$ 有两种素因子，记为 $a,b$，于是等价于求解 $ax+by=n$ 的非负整数解。 | ||
| 找到最小的 $y$ 满足 $y\equiv nb^{-1}\bmod x$，然后验证此时 $by$ 是否不超过 $n$ 即可。 | 找到最小的 $y$ 满足 $y\equiv nb^{-1}\bmod x$，然后验证此时 $by$ 是否不超过 $n$ 即可。 | ||
| 行 173: | 行 175: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | const int MAXN=5,MAXV=6e4+5; | + | const int MAXV=4e7,MAXN=1e5+5,MAXQ=1e4+5; |
| - | const LL inf=2e18; | + | const LL inf=1e18+5; |
| - | int d[MAXN]; | + | int prime[MAXV],pcnt; |
| - | vector<pair<int,int> > g[MAXN]; | + | bool vis[MAXV]; |
| - | LL dis[MAXN][MAXV]; | + | void Init(){ |
| - | bool vis[MAXN][MAXV]; | + | _for(i,2,MAXV){ |
| + | if(!vis[i])prime[pcnt++]=i; | ||
| + | for(int j=0;j<pcnt&&i*prime[j]<MAXV;j++){ | ||
| + | vis[i*prime[j]]=true; | ||
| + | if(i%prime[j]==0) | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | vector<LL> g; | ||
| + | void get_frac(LL n){ | ||
| + | g.clear(); | ||
| + | _for(i,0,pcnt){ | ||
| + | if(n%prime[i]==0){ | ||
| + | g.push_back(prime[i]); | ||
| + | while(n%prime[i]==0)n/=prime[i]; | ||
| + | } | ||
| + | } | ||
| + | if(n!=1) | ||
| + | g.push_back(n); | ||
| + | } | ||
| + | int quick_pow(int n,int k,int mod){ | ||
| + | int ans=1; | ||
| + | while(k){ | ||
| + | if(k&1)ans=1LL*ans*n%mod; | ||
| + | n=1LL*n*n%mod; | ||
| + | k>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | LL dis[MAXN]; | ||
| void dj(int n){ | void dj(int n){ | ||
| - | priority_queue<pair<LL,int> > q; | + | _for(i,0,n){ |
| - | q.push(make_pair(0,1)); | + | dis[i]=inf; |
| - | _for(i,0,4)_for(j,0,n) | + | vis[i]=false; |
| - | dis[i][j]=inf,vis[i][j]=false; | + | } |
| - | dis[1][0]=0; | + | dis[0]=0; |
| + | priority_queue<LL> q; | ||
| + | q.push(0); | ||
| while(!q.empty()){ | while(!q.empty()){ | ||
| - | int u1=q.top().second; | + | int u=(-q.top())%n;q.pop(); |
| - | int u2=(-q.top().first)%n; | + | if(vis[u]) |
| - | q.pop(); | + | |
| - | if(vis[u1][u2]) | + | |
| continue; | continue; | ||
| - | vis[u1][u2]=true; | + | vis[u]=true; |
| - | for(pair<int,int> p:g[u1]){ | + | _for(i,1,g.size()){ |
| - | int v1=p.first,w=p.second,v2=(u2+w)%n; | + | int v=(u+g[i])%n; |
| - | if(dis[v1][v2]>dis[u1][u2]+w){ | + | if(dis[v]>dis[u]+g[i]){ |
| - | dis[v1][v2]=dis[u1][u2]+w; | + | dis[v]=dis[u]+g[i]; |
| - | q.push(make_pair(-dis[v1][v2],v1)); | + | q.push(-dis[v]); |
| } | } | ||
| } | } | ||
| } | } | ||
| } | } | ||
| - | LL calc(int val,LL k){ | + | bool query(LL n){ |
| - | LL ans=inf; | + | if(g.size()==0) |
| - | _for(i,0,val){ | + | return false; |
| - | if(dis[1][i]>k) | + | if(g.size()==1) |
| - | ans=min(ans,dis[1][i]); | + | return n%g[0]==0; |
| - | else | + | else if(g.size()==2){ |
| - | ans=min(ans,dis[1][i]+(k-dis[1][i]+val-1)/val*val); | + | LL x=g[0],y=g[1]; |
| + | int b=(n%x)*quick_pow(y%x,x-2,x)%x; | ||
| + | return y*b<=n; | ||
| } | } | ||
| - | return ans; | + | else{ |
| - | } | + | int m=g[0]; |
| - | void solve(){ | + | return dis[n%m]<=n; |
| - | LL k=read_LL(); | + | |
| - | _for(i,0,4) | + | |
| - | g[i].clear(); | + | |
| - | _for(i,0,4){ | + | |
| - | d[i]=read_int(); | + | |
| - | g[i].push_back(make_pair((i+1)%4,d[i])); | + | |
| - | g[(i+1)%4].push_back(make_pair(i,d[i])); | + | |
| } | } | ||
| - | dj(2*d[0]); | + | } |
| - | enter(calc(2*d[0],k)); | + | map<LL,vector<pair<int,LL> > >mp; |
| + | bool ans[MAXQ]; | ||
| + | void solve(LL k,vector<pair<int,LL> > a){ | ||
| + | get_frac(k); | ||
| + | if(g.size()>2) | ||
| + | dj(g[0]); | ||
| + | for(pair<int,LL> p:a) | ||
| + | ans[p.first]=query(p.second); | ||
| } | } | ||
| int main(){ | int main(){ | ||
| - | int T=read_int(); | + | Init(); |
| - | while(T--) | + | int q=read_int(); |
| - | solve(); | + | _for(i,0,q){ |
| + | LL n=read_LL(),k=read_LL(); | ||
| + | mp[k].push_back(make_pair(i,n)); | ||
| + | } | ||
| + | for(map<LL,vector<pair<int,LL> > >::iterator iter=mp.begin();iter!=mp.end();iter++) | ||
| + | solve(iter->first,iter->second); | ||
| + | _for(i,0,q){ | ||
| + | if(ans[i]) | ||
| + | puts("YES"); | ||
| + | else | ||
| + | puts("NO"); | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/同余最短路.1630756530.txt.gz · 最后更改: 2021/09/04 19:55 由 jxm2001
