[ABC286F] Guess The Number 2
题意转换：
有一个数 \(n\)，你不知道是多少。让你构造一个 \(m\) 个点（\(1\le m\le 110\)），且每条边有且仅有一条出边的图。告诉你每个点沿着边走 \(n\) 次后到达的点，求 \(n\)。
思路：
可以发现当 \(n\) 很大时，每个点最终都到达了一个环内。
由于 \(n\) 很大时发现如果不是环上的边就是无意义的，仅仅是对同余方程进行了加减操作。
于是，我们考虑构造若干个环（我们假定对于大小为 \(k\) 的环，下标 \([0,k)\)，将输入输出变换一下即可得到），然后就可以得到同余方程组：（假定有 \(s\) 个方程）
\(\left\{\begin{align} n\equiv a_1(\bmod m_1)\\ n\equiv a_2(\bmod m_2)\\ \dots\\n\equiv a_s(\bmod m_s)\\ \end{align}\right.\)
我们只要让 \(m\) 两两互质，就可以用中国剩余定理求解，且两个通解之间的距离为 \(\prod m_i\)。
为了保证解的唯一性和序列长度限制，需要满足 \(\sum m_i\le 110,\prod m_i\ge 10^9\)。
取 \(2,3,5,7,11,13,17,19,23\)，发现和为 \(100\)，单乘积不过，只有约 \(2.2\times 10^8\)。
我们把 \(2,3\) 换成 \(4,9\)，则乘积就大了 \(6\) 倍，和也只大了 \(8\)，满足要求。
注意尽管最终答案不超过 \(10^9\)，但是中国剩余定理中途的答案可能超过，需要 long long。
#include<cstdio>
#include<iostream>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
const int p[]={4,9,5,7,11,13,17,19,23},N=sizeof(p)/sizeof(p[0]);
int m,mul=1;
typedef long long ll;
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(){
#ifndef ONLINE_JUDGE
// freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout<<"108\n";
int sum=1;
L(i, N){
E(j, p[i]-1)
cout<<sum+j<<' ';
cout<<sum<<' ';
sum+=p[i];
mul*=p[i];
}
cout<<endl;
sum=1;
ll ans=0;
L(i, N){
int x;
cin>>x;
//n===x-sum(mod p[i])
ll a=x-sum;
int M=mul/p[i];
int t1,t2;
exgcd(M,p[i],t1,t2);
ans+=a*M*(t1<0?t1+p[i]:t1);
L(j, p[i]-1)cin>>x;
sum+=p[i];
}
cout<<ans%mul;
return 0;
}