【数论 扩展欧几里得 中国剩余定理】P12364 [蓝桥杯 2022 省 Python B] 寻找整数|普及+

本文涉及知识点

数论：质数、最大公约数、菲蜀定理

P12364 [蓝桥杯 2022 省 Python B] 寻找整数

题目描述

有一个不超过 10 17 10^{17} 1017 的正整数 n n n，知道这个数除以 2 2 2 至 49 49 49 后的余数如下表所示，求这个正整数最小是多少。

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只需要编写一个程序输出这个整数，输出多余的内容将无法得分。

数论 扩展欧几里得 中国剩余定理

令本题答案是X, 令a[i] = 2 + i, b[i] = x % a[i]，b[i] 可以查本题的表得到。
将48个{a[i],b[i]}放到栈中。
如果栈中只有一个元素，则b就是答案。
如果栈中有2个及更多元素。分别为{a1, b1},{ a2,b2}，出栈这两个元素。
枚举 y = ( b 1 + a 1 ∗ i ) y=(b1+a1*i)%a2, y==b2 y=(b1+a1∗i), 本题有解故i不会超过a2。
y是最小解，则 y + l c m ( a 1 , a 2 ) ∗ × i y +lcm(a1, a2)*\times i y+lcm(a1,a2)∗×i都是解，故{lcm(a1,12), y}入栈。
扩展欧几里得(辗转相除发): a 1 x + b 1 = a 2 y + b 2 a1x + b1 = a2y + b2 a1x+b1=a2y+b2*方程式一 * *,方程式一的任意整数解(x1, y1)。a1x + b1就是答案。（a1x + b1)% lcm(a1, a2)，如果 < 0，则加上lcm(a1, a2)。
方程式一就是 a 1 x − a 2 y = b 2 − b 1 a1x-a2y=b2-b1 a1x−a2y=b2−b1, 如果b2-b1不是gcd(a1, a2)的倍数，无解。
如果 a 1 x − a 2 y = g c d ( a 1 , a 2 ) a1x-a2y=gcd(a1, a2) a1x−a2y=gcd(a1,a2)方程式二的任意解(x1, y1), t = (b2 - b1) / gcd(a1, a2),(tx1, ty1)都方程式一的解。

代码

核心代码

#include<iostream>#include<sstream>#include<vector>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<string>#include<algorithm>#include<functional>#include<queue>#include<stack>#include<iomanip>#include<numeric>#include<math.h>#include<climits>#include<assert.h>#include<cstring>#include<list>#include<array>#include<bitset>usingnamespace std;template<classT1,classT2> std::istream&operator>>(std::istream& in, pair<T1, T2>& pr){ in >> pr.first >> pr.second;return in;}template<classT1,classT2,classT3> std::istream&operator>>(std::istream& in, tuple<T1, T2, T3>& t){ in >>get<0>(t)>>get<1>(t)>>get<2>(t);return in;}template<classT1,classT2,classT3,classT4> std::istream&operator>>(std::istream& in, tuple<T1, T2, T3, T4>& t){ in >>get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t);return in;}template<classT1,classT2,classT3,classT4,classT5,classT6,classT7> std::istream&operator>>(std::istream& in, tuple<T1, T2, T3, T4,T5,T6,T7>& t){ in >>get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t)>>get<4>(t)>>get<5>(t)>>get<6>(t);return in;}template<classT=int> vector<T>Read(){int n; cin >> n; vector<T>ret(n);for(int i =0; i < n; i++){ cin >> ret[i];}return ret;}template<classT=int> vector<T>ReadNotNum(){ vector<T> ret; T tmp;while(cin >> tmp){ ret.emplace_back(tmp);if('\n'== cin.get()){break;}}return ret;}template<classT=int> vector<T>Read(int n){ vector<T>ret(n);for(int i =0; i < n; i++){ cin >> ret[i];}return ret;}template<int N =1'000'000>classCOutBuff{public:COutBuff(){ m_p = puffer;}template<classT>voidwrite(T x){int num[28], sp =0;if(x <0)*m_p++='-', x =-x;if(!x)*m_p++=48;while(x) num[++sp]= x %10, x /=10;while(sp)*m_p++= num[sp--]+48;AuotToFile();}voidwritestr(constchar* sz){strcpy(m_p, sz); m_p +=strlen(sz);AuotToFile();}inlinevoidwrite(char ch){*m_p++= ch;AuotToFile();}inlinevoidToFile(){fwrite(puffer,1, m_p - puffer,stdout); m_p = puffer;}~COutBuff(){ToFile();}private:inlinevoidAuotToFile(){if(m_p - puffer > N -100){ToFile();}}char puffer[N],* m_p;};template<int N =1'000'000>classCInBuff{public:inlineCInBuff(){}inline CInBuff<N>&operator>>(char& ch){FileToBuf();while(('\r'==*S)||('\n'==*S)||(' '==*S)){ S++;}//忽略空格和回车 ch =*S++;return*this;}inline CInBuff<N>&operator>>(int& val){FileToBuf();intx(0),f(0);while(!isdigit(*S)) f |=(*S++=='-');while(isdigit(*S)) x =(x <<1)+(x <<3)+(*S++^48); val = f ?-x : x; S++;//忽略空格换行 return*this;}inline CInBuff&operator>>(longlong& val){FileToBuf();longlongx(0);intf(0);while(!isdigit(*S)) f |=(*S++=='-');while(isdigit(*S)) x =(x <<1)+(x <<3)+(*S++^48); val = f ?-x : x; S++;//忽略空格换行return*this;}template<classT1,classT2>inline CInBuff&operator>>(pair<T1, T2>& val){*this>> val.first >> val.second;return*this;}template<classT1,classT2,classT3>inline CInBuff&operator>>(tuple<T1, T2, T3>& val){*this>>get<0>(val)>>get<1>(val)>>get<2>(val);return*this;}template<classT1,classT2,classT3,classT4>inline CInBuff&operator>>(tuple<T1, T2, T3, T4>& val){*this>>get<0>(val)>>get<1>(val)>>get<2>(val)>>get<3>(val);return*this;}template<classT=int>inline CInBuff&operator>>(vector<T>& val){int n;*this>> n; val.resize(n);for(int i =0; i < n; i++){*this>> val[i];}return*this;}template<classT=int> vector<T>Read(int n){ vector<T>ret(n);for(int i =0; i < n; i++){*this>> ret[i];}return ret;}template<classT=int> vector<T>Read(){ vector<T> ret;*this>> ret;return ret;}private:inlinevoidFileToBuf(){constint canRead = m_iWritePos -(S - buffer);if(canRead >=100){return;}if(m_bFinish){return;}for(int i =0; i < canRead; i++){ buffer[i]= S[i];//memcpy出错 } m_iWritePos = canRead; buffer[m_iWritePos]=0; S = buffer;int readCnt =fread(buffer + m_iWritePos,1, N - m_iWritePos,stdin);if(readCnt <=0){ m_bFinish =true;return;} m_iWritePos += readCnt; buffer[m_iWritePos]=0; S = buffer;}int m_iWritePos =0;bool m_bFinish =false;char buffer[N +10],* S = buffer;};classSolution{public:longlongAns(){longlong x =2022040920220409LL; stack<pair<longlong,longlong>> sta;for(int i =2; i <=49; i++){ sta.emplace(i,x % i);}while(sta.size()>1){auto[a, c]= sta.top(); sta.pop();auto[b, d]= sta.top(); sta.pop();for(longlong x=c;; x+=a ){if(x % b == d){ sta.emplace(lcm(a,b),x);break;}}}return sta.top().second;}};intmain(){#ifdef_DEBUGfreopen("a.in","r",stdin);#endif// DEBUG  ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob; //int N,K;//cin >>N>> K;#ifdef_DEBUG // printf("K=%d", K);// Out(a, ",a=");//Out(P, ",P=");/*Out(edge, ",edge="); Out(que, ",que=");*///Out(ab, ",ab=");//Out(par, "par=");//Out(que, "que=");//Out(B, "B=");#endif// DEBUG auto res =Solution().Ans(); cout <<res;return0;};

单元测试

TEST_METHOD(TestMethod1){auto res =Solution().Ans();AssertEx(2022040920220409LL, res);}

# 扩展阅读

视频课程

先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。