1. 全栈程序员必看首页

中国剩余定理与扩展

全栈程序员-站长 • • 未分类 • 阅读 2

中国剩余定理与扩展中国剩余定理一开始觉得这东西好难 后来发现好像也没有这么难 我们来看一道题目 树王种了一棵 treap 她现在决定把这棵 treap 改造为一棵无旋多叉 triep 于是她摘下了 treap 的所有节点 发现如果她把节点 3 个 3 个一打包 会剩下 2 个节点 如果她把节点 5 个 5 个一打包 会剩下 3 个节点 如果把节点 7 个 7 个一打包 会剩下 2 个节点 求这棵 treap 最少有多少节点 首先假如我们求出这样三个

中国剩余定理

树王种了一棵treap，她现在决定把这棵treap改造为一棵无旋多叉triep，于是她摘下了treap的所有节点，发现如果她把节点3个3个一打包，会剩下2个节点。如果她把节点5个5个一打包，会剩下3个节点，如果把节点7个7个一打包，会剩下2个节点，求这棵treap最少有多少节点？

首先假如我们求出这样三个数 k1,k2,k3 k 1 , k 2 , k 3 ，满足k1模3余1且是5和7的倍数，k2模5余1且是3,7的倍数，k3模7余1且是3和5的倍数，那么容易意会得到， k1∗2+k2∗3+k3∗2 k 1 ∗ 2 + k 2 ∗ 3 + k 3 ∗ 2 一定会是一个满足题目条件的数。而题目的通解可表示为这个数每次都加上3,5,7的最小公倍数

#include 
    #include 
    #include 
    #include 
    #include 
    using namespace std; int n,m[105],a[105],lcm=1; int exgcd(int a,int b,int &x,int &y){ 
  //扩欧 if(!b){x=1,y=0;return a;} int re=exgcd(b,a%b,x,y),tmp=x; x=y,y=tmp-(a/b)*y; return re; } int work(){ int i,j,d,x,y,re=0; for(i=1;i<=n;i++)lcm=lcm*m[i];//因为互质所以直接这么写了 for(i=1;i<=n;i++){ int kl=lcm/m[i]; d=exgcd(kl,m[i],x,y); x=(x%m[i]+m[i])%m[i]; re=(re+a[i]*x*kl)%lcm; } return re; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&m[i],&a[i]);; printf("%d",work()); return 0; }

扩展中国剩余定理

#include 
    #include 
    #include 
    #include 
    #include 
    using namespace std; #define LL long long const int maxn=1e5+5; int n; LL exgcd(LL a,LL b,LL &x,LL &y){ if(!b){x=1,y=0;return a;} LL re=exgcd(b,a%b,x,y),tmp=x; x=y,y=tmp-(a/b)*y; return re; } LL m[maxn],a[maxn]; LL work(){ LL M=m[1],A=a[1],t,d,x,y;int i; for(i=2;i<=n;i++){ d=exgcd(M,m[i],x,y);//解方程 if((a[i]-A)%d)return -1;//无解 x*=(a[i]-A)/d,t=m[i]/d,x=(x%t+t)%t;//求x A=M*x+A,M=M/d*m[i],A%=M;//日常膜一膜（划掉）模一模，防止爆 } A=(A%M+M)%M; return A; } int main() { int i,j; while(scanf("%d",&n)!=EOF){ for(i=1;i<=n;i++)scanf("%lld%lld",&m[i],&a[i]); printf("%lld\n",work()); } return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/216681.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月18日 上午11:18
下一篇 2026年3月18日 上午11:19


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号