题解
这里给出一种傻逼做法,同余系最短路,
所谓同余系最短路并不是拿同余方程跑最短路,而是跑最短路用同余方程优化
时间700毫,可以拓展到任意多元方程情况,任意起点情况$(k_1*x_1+k_2*x_2+k_3*x_3+k_4*x_4.......)$
把$x_1$等抽象成步数,
考虑简单容斥,拿$q-可以达到的解$
在得出一个可以达到的解我们可以任意拓展+任意多别的数达到其他值,我们可以利用这一优良性质
例如现在有$x=1,y=3$,$y$可以达到$3$那么我们可以$3+1*x,3+2*x,3+3*x$得到其他所有解,解的个数就是$(q-dis[i])/n+1$
于是构造在同余于$x$下的同余系,$dis[i]$表示在$\%x后=i$需要的最少步数
考虑暴力$dp$ $dis[(i+y)\%x]=min(dis[i]+y)$,形式相当于最短路形式,建从$i->(i+y)\%x$边跑$spfa$即可
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 555555
ll head[A],nxt[A],ver[A],edg[A],dis[A],vis[A];
ll t,tot,n,m,q;
void add(ll x,ll y,ll z){
nxt[++tot]=head[x],head[x]=tot,ver[tot]=y,edg[tot]=z;
}
void spfa(ll o){
memset(dis,63,sizeof(dis));
memset(vis,0,sizeof(vis));
deque<ll> q;
dis[0]=0;
vis[0]=1;
q.push_back(0);
while(!q.empty()){
ll x=q.front();
q.pop_front();
for(ll i=head[x];i;i=nxt[i]){
ll y=ver[i];
if(dis[y]>dis[x]+edg[i]){
dis[y]=dis[x]+edg[i];
if(!vis[y]){
vis[y]=1;
q.push_back(y);
}
}
}
vis[x]=0;
}
}
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld",&n,&m,&q);
if(n>m) swap(n,m);//n较小值
memset(head,0,sizeof(head));
memset(nxt,0,sizeof(nxt));
tot=0;
for(ll i=0;i<n;i++){
add(i,(i+m)%n,m);
}
spfa(0);
ll ans=0;
for(ll i=0;i<n;i++){
if(dis[i]<=q)
ans+=(q-dis[i])/n+1;
}
ans--;
printf("%lld\n",q-ans);
}
}