Home php教程 php手册 Hello Kiki&&http://acm.hdu.edu.cn/showproble

Hello Kiki&&http://acm.hdu.edu.cn/showproble

Jun 13, 2016 am 10:50 AM
amp http pid

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
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

What does http status code 520 mean? What does http status code 520 mean? Oct 13, 2023 pm 03:11 PM

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 common application scenarios of web page redirection and understand the HTTP 301 status code Understand common application scenarios of web page redirection and understand the HTTP 301 status code Feb 18, 2024 pm 08:41 PM

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 Nginx Proxy Manager to implement automatic jump from HTTP to HTTPS How to use Nginx Proxy Manager to implement automatic jump from HTTP to HTTPS Sep 26, 2023 am 11:19 AM

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

What is http status code 403? What is http status code 403? Oct 07, 2023 pm 02:04 PM

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.

http request 415 error solution http request 415 error solution Nov 14, 2023 am 10:49 AM

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 Quick Application: Practical Development Case Analysis of PHP Asynchronous HTTP Download of Multiple Files Sep 12, 2023 pm 01:15 PM

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# Common network communication and security problems and solutions in C# Oct 09, 2023 pm 09:21 PM

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 using C++? How to implement HTTP streaming using C++? May 31, 2024 am 11:06 AM

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.

See all articles