脚本宝典收集整理的这篇文章主要介绍了2021.08.12 孙子定理系列，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
P1495 【模板】中国剩余定理(CRT)/曹冲养猪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
//刚打过孙子定理进阶版，现在直接打孙子定理
//x~b_1*M_1'*M_1+b_2*M_2'*M_2+…+b_k*M_k'*M_k(mod M)
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m[N],b[N];
ll M=1,ans,x,y;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1,y=0;
return ;
}
exgcd(b,a%b,x,y);
ll xi=x;
x=y;y=xi-(a/b)*y;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
m[i]=read();b[i]=read();
M*=m[i];
}
//cout<<"M "<<M<<endl;//
for(int i=1;i<=n;i++){
ll Mi=M/m[i];
exgcd(Mi,m[i],x,y);
if(x<0)x+=m[i];
ans+=b[i]*Mi*x;
}
cout<<ans%M;
return 0;
}
P4549 【模板】裴蜀定理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
//虽然说是裴蜀定理，但是我依旧执着地认为这是不定方程的解法
//ax+by=c有解要求(a,b)|c，则当c=(a,b)时，c最小
//因此用gcd
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,ans;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
int main(){
n=read();
ans=read();
for(int i=2;i<=n;i++){
int x=read();
ans=gcd(ans,x>0?x:-x);
}
cout<<ans;
return 0;
}
P4777 【模板】扩展中国剩余定理（EXCRT） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
//求同余方程，详情参考《初等数论1》第四章习题第七题、第八题
//换而言之，就是孙子定理的进阶版——任取m_i、m_j，(m_i,m_j)不一定等于1
//这里求出x0
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll n,b[N],m[N];
ll ans,M,x,y;//M 为最小公倍数
inline ll read(){
ll s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b)return x=1,y=0,a;
ll d=exgcd(b,a%b,x,y);
ll xi=x;
return x=y,y=xi-(a/b)*y,d;
}
ll mul(ll x,ll k,ll p){
ll fin=0;
while(k){
if(k&1)fin=(fin+x)%p;
x=(x+x)%p;
k>>=1;
}
return fin;
}
int main(){
n=read();
for(int i=1;i<=n;i++)m[i]=read(),b[i]=read();
ans=b[1];
M=m[1];
//ans+x*M~b_i(mod m_i)
//x*M~b_i-ans(mod m_i)
//x*M~((b_i-ans)%m_i+m_i)%m_i(mod m_i)
for(int i=2;i<=n;i++){
ll bi=((b[i]-ans)%m[i]+m[i])%m[i];
ll gcd=exgcd(M,m[i],x,y);
x=mul(x,bi/gcd,m[i]);
ans+=x*M;
M*=m[i]/gcd;
ans=(ans+M)%M;
}
cout<<ans;
return 0;
}
[P3868 TJOI2009]猜数字 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
//b_i|(n-a_i)->n~a_i(mod b_i)，(b_i,b_j)=1
//好吧，又转化为孙子定理了~
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m[15],b[15];
ll M=1,ans,x,y;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1,y=0;
return ;
}
exgcd(b,a%b,x,y);
ll xi=x;
x=y;y=xi-(a/b)*y;
}
ll mul(ll a,ll k,ll mod){
ll fin=0;
while(k){
if(k&1)fin=(fin+a)%mod;
a=(a+a)%mod;
k>>=1;
}
return fin;
}
int main(){
n=read();
for(int i=1;i<=n;i++)b[i]=read();
for(int i=1;i<=n;i++)m[i]=read(),M*=m[i];
for(int i=1;i<=n;i++){
ll Mi=M/m[i];
exgcd(Mi,m[i],x,y);
if(x<0)x+=m[i];
ans=(ans+mul(b[i],mul(Mi,x,M),M))%M;
}
cout<<ans%M;
return 0;
}
P5091 【模板】扩展欧拉定理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
//很难想，还没推出来扩展欧拉定理
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
ll a,b,m;
inline ll read(){
ll s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline ll readi(ll m){
ll s=0,flag=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){
s=s*10+ch-'0';
if(s>=m)flag=1;
s%=m;
ch=getchar();
}
return s+(flag==1?m:0);
}
ll oula(ll x){
ll fin=x,xi=x;
for(ll i=2;i*i<=xi;i++){
if(x%i==0){
fin=fin/i*(i-1);
while(x%i==0)x/=i;
}
}
if(x>1)fin=fin/x*(x-1);
return fin;
}
ll mul(ll x,ll k,ll p){
ll fin=0;
while(k){
if(k&1)fin=(fin+x)%p;
x=(x+x)%p;
k>>=1;
}
return fin;
}
ll pow(ll x,ll k,ll p){
ll fin=1;
while(k){
if(k&1)fin=mul(fin,x,p);
x=mul(x,x,p);
k>>=1;
}
return fin;
}
int main(){
a=read();m=read();
//cout<<" case 1"<<endl;
b=readi(oula(m));
//cout<<" case 2"<<endl;
cout<<pow(a,b,m);
return 0;
}
以上是脚本宝典为你收集整理的2021.08.12 孙子定理系列全部内容，希望文章能够帮你解决2021.08.12 孙子定理系列所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。