1079 中国剩余定理
1.0 秒
131,072.0 KB
0 分
基础题
一个正整数 K, 给出 K Mod 一些质数的结果, 求符合条件的最小的 K. 例如, K % 2 = 1, K % 3 = 2, K % 5 = 3. 符合条件的最小的 K = 23.
输入
第 1 行: 1 个数 N 表示后面输入的质数及模的数量.(2 <= N <= 10)
第 2 - N + 1 行, 每行 2 个数 P 和 M, 中间用空格分隔, P 是质数, M 是 K % P 的结果.(2 <= P <= 100, 0 <= K <P)
输出
输出符合条件的最小的 K. 数据中所有 K 均小于 10^9.
输入样例
3 2 1 3 2 5 3
输出样例
23
代码
- #include<cstdio>
- #include<iostream>
- using namespace std;
- #define ll long long
- ll a[20],p[20],b[20];
- ll power(ll x,ll p1)
- {
- ll b=p1-2,sum=1;
- while(b)
- {
- if(b&1)
- sum=(sum*x)%p1;
- x=(x*x)%p1;
- b=b>>1;
- }
- return sum;
- }
- int main()
- {
- ll n,M=1,sum=0;
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>a[i]>>p[i];
- M=M*a[i];
- }
- for(int i=1;i<=n;i++)
- {
- b[i]=M/a[i];
- }
- for(int i=1;i<=n;i++)
- {
- ll x=b[i]*power(b[i],a[i]);
- sum=(sum+p[i]*x)%M;
- // cout<<sum<<"\n";
- }
- cout<<sum<<"\n";
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3093623.html