用到中国剩余定理,然后用扩展欧几里得算法求解。
这里有两个注意点,1、硬币数量不能为0或者负数
2、每个group数量有可能大于50,样例中就有
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int M[10],A[10],n;
int extEuclid(int p,int q,int &x,int &y)//扩展欧几里得算法
{
int d,tmp;
if(q==0){x=1;y=0;return p;}
d=extEuclid(q,p%q,x,y);
tmp=x;x=y;y=tmp-p/q*y;
return d;//返回最大公约数
}
int calcu(int cur)
{
int x,y,g,t;
int a1=M[cur-1],a2=M[cur];
int b1=A[cur-1],b2=A[cur];
g=extEuclid(a1,a2,x,y);
int s=b2-b1;
if(s%g)
return -1;
else
{
t=a2/g;
x=x*s/g;//这个一定要放在“x=(x%t+t)%t”前面,否则就wa了
x=(x%t+t)%t;//求出在0~t之间的一个解。这一步必须有,否则就wa,因为爆int了,可改成long long,改过后也可以ac
a2=a1*a2/g;
s=((a1*x+b1)%a2+a2)%a2;
A[cur]=s;
M[cur]=a2;
if(cur==n-1)
{
if(s==0)
return M[cur];
else
return A[cur];
}
else
return calcu(cur+1);
}
}
int main()
{
int i,j,k,t;
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&M[i]);
for(i=0;i<n;i++)
scanf("%d",&A[i]);
printf("Case %d: ",k);
if(n==1)
{
if(A[0]==0)
A[0]=M[0];
printf("%d\n",A[0]);
continue;
}
printf("%d\n",calcu(1));
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
此程序为hdu的acm2010题,就是解决水仙花数问题
杭电hdu acm资料所用杭电的acm题
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
hdu 1005.比较简单的一道题,有兴趣的可以看看。
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
100道 acm C语言 hdu 解题报告
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
HDU1059的代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU2013暑期多校联合训练第一场0723-解题报告和标程
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)