搜索
首页php教程php手册Hello Kiki&&http://acm.hdu.edu.cn/showproble

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
声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热工具

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。