2015-05-27
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 <= i <= N) on the second line, and corresponding Ai(1 <= i <= N) on the third line.
All numbers in the input and output are integers.
1 <= T <= 100, 1 <= N <= 6, 1 <= Mi <= 50, 0 <= Ai < Mi
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<iostream>
#include<string.h>
#include<string>
#include<cstdio>
#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<=T;++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<n;++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;
}
1
CI框架连接数据库配置操作以及多数据库操作
09-05
2
asp 简单读取数据表并列出来 ASP如何快速从数据库读取大量数据
05-17
3
C语言关键字及其解释介绍 C语言32个关键字详解
04-05
4
C语言中sizeof是什么意思 c语言里sizeof怎样用法详解
04-26
5
最简单的asp登陆界面代码 asp登陆界面源代码详细介绍
04-12
6
PHP中的魔术方法 :__construct, __destruct , __call, __callStatic,__get, __set, __isset, __unset , __sleep,
09-05
7
PHP中的(++i)前缀自增 和 (i++)后缀自增
09-05
8
PHP中include和require区别之我见
09-05
常用dos命令及语法
2014-09-27
将视频设置为Android手机开机动画的教程
2014-12-11
php递归返回值的问题
2014-09-05
如何安装PHPstorm并配置方法教程 phpstorm安装后要进行哪些配置
2017-05-03
java中的info是什么意思
2022-03-24
IcePHP框架中的快速后台中的通用CRUD功能框架
2014-09-05
PHP 教程之如何使用BLOB存取图片信息实例
2014-09-05
单片机编程好学吗?单片机初学者怎样看懂代码
2022-03-21
PHP数组函数array
2014-09-05
学ug编程如何快速入门?
2022-03-17
无尽洪荒手游正版下载v10.0.83 安卓最新版本
角色扮演 32.7M
下载美职篮巅峰对决游戏下载v1.6.400 安卓版
体育运动 1.31G
下载朕的江山手游下载v2.17.31 安卓正式版
策略塔防 1.66G
下载保卫萝卜3官方正版下载v5.2.0 安卓最新版本
休闲益智 551.4M
下载奥特曼之格斗超人最新版本下载v12.0.0 安卓手机版
动作闯关 639.8M
下载三国志幻想大陆官方正版下载v5.9.0 安卓最新版
卡牌对战 741.0M
下载狂野钓鱼2无限钻石版下载v1.0.9 安卓破解版内置菜单
休闲益智 172.4M
下载网易赤痕夜之仪式手游版(bloodstainedrotn)下载v1.34 安卓版
角色扮演 1.65G
下载碉少堡独立服海岛奇兵下载v60.1.2 安卓版
下载
海岛奇兵联想版本下载v60.1.2 安卓版
下载
火影忍者木叶高手游戏下载v1.0.2 安卓版
下载
海岛奇兵网易云版下载v60.1.2 安卓版
下载
刀塔霸业手游(Underlords)下载v1.1.0 安卓版
下载
海岛奇兵微信版本下载v60.1.2 安卓版
下载
海岛奇兵华为账号登录版下载v60.1.2 安卓版
下载
海岛奇兵拇指玩版本下载v60.1.2 安卓版
下载