链接

　　http://codevs.cn/problem/3040/

题解

　　中国剩余定理。 　　对于方程组 　　

⎧⎩⎨⎪⎪⎪⎪⎪⎪x=a1(mod m1)x=a2(mod m2)...x=an(mod mn) 　　解的构造方法是 　　 M=m1m2m3...mkMi=Mmians=∑i=1naiMiM−1i 　　其中 M−1i 是 Mi 在模 mi 意义下的逆元 　　 ans mod M 就是最小的正整数解

代码

//中国剩余定理 #include <cstdio> #include <algorithm> #define maxn 100 #define ll long long using namespace std; ll m[maxn], a[maxn]; void exgcd(ll a, ll b, ll &x, ll &y) { if(!b){x=1,y=0;return;} ll xx, yy; exgcd(b,a%b,xx,yy); x=yy,y=xx-a/b*yy; } ll inv(ll a, ll p) { ll x, y; exgcd(a,p,x,y); return (x+p)%p; } ll crt(ll *a, ll *m, ll n) { ll M=1, Mi, x, ans=0, i; for(i=1;i<=n;i++)M=M*m[i]; for(i=1;i<=n;i++) { Mi=M/m[i]; x=inv(Mi,m[i]); ans=ans+a[i]*Mi*x; } return ans%M; } int main() { ll k, ans; scanf("%lld",&k); a[1]=2, a[2]=3, a[3]=2; m[1]=3, m[2]=5, m[3]=7; ans=crt(a,m,3); ans+=(k-1)*105; printf("%lld\n",ans); return 0; }