本文共 1985 字，大约阅读时间需要 6 分钟。
结果看了半天还是没懂那个模的含义...懂了我再补充...
其他的思路都在注释里
/********************* Template ************************/#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define EPS 1e-8#define MAXN (int)1e5+100#define MOD (int)1e9+7#define PI acos(-1.0)#define LINF ((1LL)<<50)#define INF (1<<30);#define max(a,b) ((a) > (b) ? (a) : (b))#define min(a,b) ((a) < (b) ? (a) : (b))#define max3(a,b,c) (max(max(a,b),c))#define min3(a,b,c) (min(min(a,b),c))#define BUG cout<<"BUG! "< > 1)#define lowbit(a) (a & -a)#define FIN freopen("in.txt","r",stdin)#define FOUT freopen("out.txt","w",stdout)#pragma comment (linker,"/STACK:102400000,102400000")typedef long long LL;// typedef unsigned long long ULL;// typedef __int64 LL;// typedef unisigned __int64 ULL;LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; }LL lcm(LL a,LL b){ return a/gcd(a,b)*b; }/********************* F ************************/LL a[MAXN],r[MAXN];bool flag;pair ex_gcd(LL a,LL b){ if(b == 0) return make_pair(1,0); pair t = ex_gcd(b,a%b); return make_pair(t.second , t.first - (a / b) * t.second);}LL work(int n){ LL a0 = a[0],r0 = r[0]; LL tmp,agcd,pr; for(int i = 1 ; i < n ; i++){ pair p = ex_gcd(a0,a[i]); agcd = gcd(a0,a[i]); pr = r[i] - r0; if(pr % agcd) { // pr%agcd==0 保证有解 flag = true; return 0; } // 不明这个模的意义,本来是要%a[i]的现在 放大了(pr/agcd)倍,估计是/pr求逆元的思想吧 tmp = a[i] / agcd; //还原方程 : p.first*a0≡pr(mod a[i]) p.first = (pr / agcd * p.first % tmp + tmp) % tmp; r0 = r0 + a0 * p.first; // 满足两个方程最小整数 a0 = a0 / agcd * a[i] ; // a0=LCM(a0,a[i]) 保证解的最小...具体为什么本弱说不清 } return r0;}int main(){ //FIN; //FOUT int n; while(cin>>n){ flag = false; for(int i = 0 ; i < n ; i++) cin>>a[i]>>r[i]; LL ans = work(n); if(flag) cout<<"-1"<
转载于:https://www.cnblogs.com/Felix-F/p/3269078.html