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
PHP中的魔术方法 :__construct, __destruct , __call, __callStatic,__get, __set, __isset, __unset , __sleep,
09-05
6
PHP中的(++i)前缀自增 和 (i++)后缀自增
09-05
7
最简单的asp登陆界面代码 asp登陆界面源代码详细介绍
04-12
8
常用dos命令及语法
09-27
PHP中include和require区别之我见
2014-09-05
将视频设置为Android手机开机动画的教程
2014-12-11
php递归返回值的问题
2014-09-05
如何安装PHPstorm并配置方法教程 phpstorm安装后要进行哪些配置
2017-05-03
PHP 教程之如何使用BLOB存取图片信息实例
2014-09-05
java中的info是什么意思
2022-03-24
单片机编程好学吗?单片机初学者怎样看懂代码
2022-03-21
学ug编程如何快速入门?
2022-03-17
PHP数组函数array
2014-09-05
IcePHP框架中的快速后台中的通用CRUD功能框架
2014-09-05
海底大鱼吃小鱼游戏下载v1.0.38 安卓版
其它手游 48.7M
下载大鱼吃小鱼保卫战游戏下载v1.0.38 安卓版
其它手游 48.7M
下载宝宝玩排序游戏下载v9.88.00.00 官方安卓版
其它手游 92.3M
下载宝宝捉迷藏宝宝巴士游戏下载v9.88.00.00 安卓最新版
其它手游 99.9M
下载泡泡小镇游乐园游戏下载v2.1.1 安卓版
休闲益智 136.6M
下载全民来装修手机版下载v1.0.1 安卓版
休闲益智 105.7M
下载指尖音符游戏免费版下载v1.0.1 安卓版
其它手游 59.5M
下载指画星河手游下载v1.0.7 安卓官方版
休闲益智 92.2M
下载蛇蛇争霸赛最新版下载v8.9.2 安卓版
下载
狂奔打耳光游戏下载v1.7.3 安卓版
下载
火箭大逃杀手游下载v2.3.7 安卓版
下载
蛋仔派对港台服最新版下载v1.0.214 安卓版
下载
花之舞九游官方版下载v1.3.9 安卓版
下载
花之舞最新版本下载v1.3.9 安卓版
下载
纵横旅人游戏下载v1.1.21 安卓版
下载
道友请留步正版手游下载v7.10.090301 安卓版
下载