Hello Kiki&&http://acm.hdu.edu.cn/showproble_PHP教程
- WBOY原创
- 2016-07-13 17:52:261207浏览
Problem Description
One day I was shopping in the supermarket. There was a cashier counting coins seriously when a little kid running and singing "门前大桥下游过一群鸭，快来快来 数一数，二四六七八". And then the cashier put the counted coins back morosely and count again...
Hello Kiki is such a lovely girl that she loves doing counting in a different way. For example, when she is counting X coins, she count them N times. Each time she divide the coins into several same sized groups and write down the group size Mi and the number of the remaining coins Ai on her note.
One day Kiki's father found her note and he wanted to know how much coins Kiki was counting.
Input
The first line is T indicating the number of test cases.
Each case contains N on the first line, Mi(1
All numbers in the input and output are integers.
1
Output
For each case output the least positive integer X which Kiki was counting in the sample output format. If there is no solution then output -1.
Sample Input
2
2
14 57
5 56
5
19 54 40 24 80
11 2 36 20 76
Sample Output
Case 1: 341
Case 2: 5996
题意：给你多种不同的数钱的方法，求满足要求的最少的钱数。
思路：猛然间一看好像是关于中国剩余定理的题，但是这一题的模数不一定是两两互质。因此可以用解模线性方程组的方法来做，这就要求必须了解扩展欧几里得算法，下面说一下解模线性方程组的方法，思想：不断的进行两两合并，即可求得。我们先可以先找两个同余方程 设通解为N,N=r1(mod(m1)),N=r2(mod(m2)),显然可以化为k1*m1+r1=k2*m2+r2;--->k1*m1+(-k2*m2)=r2-r1;设a=m1,b=m2,x=k1,y=(-k2),c=r2-r1方程可写为ax+by=c;由扩展欧几里得解得x即可,那么将x化为原方程的最小正整数解，(x*(c/d)%(b/d)+(b/d))%(b/d);那么这个x就是原方程的最小整数解。所以N=a*（x+n*（b/d））+r1====N=(a*b/d)*n+(a*x+r1),这里只有n为未知数所以又是一个N=(a*x+r1)(mod(a*b/d))的式子，然后只要不断的将两个式变成一个式子，最后就能解出这个方程组的解
AC代码：
[cpp]
#include
#include
#include
#include
#define N 7
using namespace std;
int M[N],A[N];
int Gcd(int a,int b)
{return b==0?a:Gcd(b,a%b);}
void gcd(int a,int b,int &d,int &x,int &y)
{
if(!b) x=1,y=0,d=a;
else gcd(b,a%b,d,y,x),y-=a/b*x;
}
int main()
{
int T;
scanf("%d",&T);
for(int k=1;k
{
int n;
scanf("%d",&n);
for(int i=0;i!=n;++i) scanf("%d",&M[i]);
for(int i=0;i!=n;++i) scanf("%d",&A[i]);
int x,y,d;
int a=M[0],c1=A[0];
bool flag=false;
for(int i=1;i
int b=M[i];
int c=A[i]-c1;
gcd(a,b,d,x,y);
if(c%d){flag=true;break;}
int r=b/d;
x=(c/d*x%r+r)%r;
c1=a*x+c1;
a=a*r;
}
if(flag) printf("Case %d: -1\n",k);
else
{
int ans=1;
if(c1==0)//特殊情况当所有余数都为0时
{
for(int i=0;i!=n;++i)
ans=M[i]/Gcd(ans,M[i])*ans;
printf("Case %d: %d\n",k,ans);
}
else printf("Case %d: %d\n",k,c1);
}
}return 0;
}
作者：smallacmer