http://prayer.hustoj.com/problem.php?id=1770 我们 口胡 证明一下； a%p=a%q=x; tp+x=a=t’q+x; ∴tp=t’q; ∵(p,q)==1; 所以 tp=t’q; 即 kqp=k’pq=tp=t’q; kqp+x=a; a%(qp)=x;
#include<iostream> #include<cstdio> #include<cstring> #define Ll long long using namespace std; const Ll NN=1e8; const int N=8; struct H{ Ll a[1250],len; H(){memset(a,0,sizeof a);len=1;} void clear(){memset(a,0,sizeof a);len=1;} }; void init(H &a){ string s; cin>>s; int l; a.len=0; for(int r=s.length()-1;r>=0;r-=N){ a.a[++a.len]=0; if(r>=N-1)l=r-N+1;else l=0; for(int i=l;i<=r;i++)a.a[a.len]=a.a[a.len]*10+s[i]-48; } } void outit(H a){ printf("%lld",a.a[a.len]); for(int i=a.len-1;i;i--){ for(int k=NN/10;a.a[i]<k;k/=10)printf("0"); if(a.a[i])printf("%lld",a.a[i]); }printf("\n"); } int main() { H s; init(s); outit(s); }