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

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

HTTP status code 520 means that the server encountered an unknown error while processing the request and cannot provide more specific information. Used to indicate that an unknown error occurred when the server was processing the request, which may be caused by server configuration problems, network problems, or other unknown reasons. This is usually caused by server configuration issues, network issues, server overload, or coding errors. If you encounter a status code 520 error, it is best to contact the website administrator or technical support team for more information and assistance.

Understand the meaning of HTTP 301 status code: common application scenarios of web page redirection. With the rapid development of the Internet, people's requirements for web page interaction are becoming higher and higher. In the field of web design, web page redirection is a common and important technology, implemented through the HTTP 301 status code. This article will explore the meaning of HTTP 301 status code and common application scenarios in web page redirection. HTTP301 status code refers to permanent redirect (PermanentRedirect). When the server receives the client's

How to use NginxProxyManager to implement automatic jump from HTTP to HTTPS. With the development of the Internet, more and more websites are beginning to use the HTTPS protocol to encrypt data transmission to improve data security and user privacy protection. Since the HTTPS protocol requires the support of an SSL certificate, certain technical support is required when deploying the HTTPS protocol. Nginx is a powerful and commonly used HTTP server and reverse proxy server, and NginxProxy

HTTP status code 403 means that the server rejected the client's request. The solution to http status code 403 is: 1. Check the authentication credentials. If the server requires authentication, ensure that the correct credentials are provided; 2. Check the IP address restrictions. If the server has restricted the IP address, ensure that the client's IP address is restricted. Whitelisted or not blacklisted; 3. Check the file permission settings. If the 403 status code is related to the permission settings of the file or directory, ensure that the client has sufficient permissions to access these files or directories, etc.

Solution: 1. Check the Content-Type in the request header; 2. Check the data format in the request body; 3. Use the appropriate encoding format; 4. Use the appropriate request method; 5. Check the server-side support.

Quick Application: Practical Development Case Analysis of PHP Asynchronous HTTP Download of Multiple Files With the development of the Internet, the file download function has become one of the basic needs of many websites and applications. For scenarios where multiple files need to be downloaded at the same time, the traditional synchronous download method is often inefficient and time-consuming. For this reason, using PHP to download multiple files asynchronously over HTTP has become an increasingly common solution. This article will analyze in detail how to use PHP asynchronous HTTP through an actual development case.

Common network communication and security problems and solutions in C# In today's Internet era, network communication has become an indispensable part of software development. In C#, we usually encounter some network communication problems, such as data transmission security, network connection stability, etc. This article will discuss in detail common network communication and security issues in C# and provide corresponding solutions and code examples. 1. Network communication problems Network connection interruption: During the network communication process, the network connection may be interrupted, which may cause

How to implement HTTP streaming in C++? Create an SSL stream socket using Boost.Asio and the asiohttps client library. Connect to the server and send an HTTP request. Receive HTTP response headers and print them. Receives the HTTP response body and prints it.
