蓝桥杯 省赛 寻找整数
– 做题记录
题目
思路 : 考虑先扩展中国剩余定理合并一些同余方程,然后再从小到大枚举a,判断是否满足所有同余式,判断是否是正确解。
不开__int128会爆ll
#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int (a) = (b) ; (a) < (c) ; ++(a))
using namespace std;
using ll = __int128 ;
using pii = pair<int,int> ;
const int maxn = 2e5 + 10 ;
char CH,NUM[40];bool F;int LEN;
template <typename T>
inline void W(T x) {
if (!x){ putchar('0'); return ;} LEN = 0;
if (x < 0) putchar('-'), x = -x;
while(x) NUM[++LEN] = (x - x / 10 * 10 ) + 48, x /= 10;
while(LEN) putchar(NUM[LEN--]);
}
int a[maxn],m[maxn] ;
inline ll gcd(ll a,ll b){
return b ? gcd(b,a % b) : a ;
}
inline void exgcd(ll a,ll b,ll &x,ll &y){
if (!b) x = 1,y = 0;
else {
exgcd(b,a % b,y,x) ;
y -= a / b * x ;
}
}
int main(){
int n ;
cin >> n ;
rep(i,1,n + 1)
cin >> m[i] >> a[i] ;
ll A = a[1],M = m[1] ;
rep(i,2,n + 1) {
ll m1 = M,m2 = m[i] ;
ll d = gcd(m1,m2) ;
ll inv,t;
exgcd(m1 / d,m2 / d,inv,t) ;
t = m2 / d ;
inv = (inv % t + t) % t ;
M = m1 * m2 / d ;
A = (m1 / d * (a[i] - A) % M * inv % M + A) % M + M ;
A %= M ;
}
ll a = A ,t = M;
a -= t;
while (true) {
a += t ;
if (a % 2 != 1 ) continue ;
if (a % 3 != 2 ) continue ;
if (a % 4 != 1 ) continue ;
if (a % 5 != 4 ) continue ;
if (a % 6 != 5 ) continue ;
if (a % 7 != 4 ) continue ;
if (a % 8 != 1 ) continue ;
if (a % 9 != 2 ) continue ;
if (a % 10 != 9 ) continue ;
if (a % 11 != 0 ) continue ;
if (a % 12 != 5 ) continue ;
if (a % 13 != 10 ) continue ;
if (a % 14 != 11 ) continue ;
if (a % 15 != 14 ) continue ;
if (a % 16 != 9 ) continue ;
if (a % 17 != 0 ) continue ;
if (a % 18 != 11 ) continue ;
if (a % 19 != 18 ) continue ;
if (a % 20 != 9 ) continue ;
if (a % 21 != 11 ) continue ;
if (a % 22 != 11 ) continue ;
if (a % 23 != 15 ) continue ;
if (a % 24 != 17 ) continue ;
if (a % 25 != 9 ) continue ;
if (a % 26 != 23 ) continue ;
if (a % 27 != 20 ) continue ;
if (a % 28 != 25 ) continue ;
if (a % 29 != 16 ) continue ;
if (a % 30 != 29 ) continue ;
if (a % 31 != 27 ) continue ;
if (a % 32 != 25 ) continue ;
if (a % 33 != 11 ) continue ;
if (a % 34 != 17 ) continue ;
if (a % 35 != 4 ) continue ;
if (a % 36 != 29 ) continue ;
if (a % 37 != 22 ) continue ;
if (a % 38 != 37 ) continue ;
if (a % 39 != 23 ) continue ;
if (a % 40 != 9 ) continue ;
W(a);
return 0 ;
}
return 0;
}