杭电ACM基础题（1017、1019、1021、1028、1029）

1017、A Mathematical Curiosity

Given two integers n and m, count the number of pairs of integers (a,b) such that 0 < a < b < n and (a²+b² +m)/(ab) is an integer.
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.【两个块之间有空行，说明最后一块不需要输出空行】
Input
You will be given a number of cases in the input. Each case is specified by a line containing the integers n and m. The end of input is indicated by a case in which n = m = 0. You may assume that 0 < n <= 100.
Output
For each case, print the case number as well as the number of pairs (a,b) satisfying the given property. Print the output for each case on one line in the format as shown below.
Sample Input

1
10 1
20 3
30 4
0 0

Sample Output

Case 1: 2
Case 2: 4
Case 3: 5

Code:
1、判断一个数double类型的数是否为整数，可以使用fmod(a,1)函数，若其结果为0，则其为整数
2、判断int类型的a和b,a/b是否为整数，可以判断a%b==0
3、注意输出的格式要求

#include<iostream> 
#include<math.h>
using namespace std;
int main(){
    int N,m,n,count;while(cin>>N){
    //cout<<endl;for(int j=0;j<N;j++){
    int i=0;while(cin>>n>>m){
    if(n==0&&m==0) break;double a,b,result;count=0;for(b=n-1;b>0;b--){
    for(a=b-1;a>0;a--){
    result=(pow(a,2)+pow(b,2)+m)/(a*b);if(fmod(result,1)==0)count++;}}i++;cout<<"Case "<<i<<": "<<count<<endl;}if(N!=1&&j!=(N-1))cout<<endl;}}return 0;
}

1019、Least Common Multiple

The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.
Input
Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 … nm where m is the number of integers in the set and n1 … nm are the integers. All integers will be positive and lie within the range of a 32-bit integer.
Output
For each problem instance, output a single line containing the corresponding LCM. All results will lie in the range of a 32-bit integer.
Sample Inupt

2
3 5 7 15
6 4 10296 936 1287 792 1

Sample Output

105
10296

Code:
1、寻找a、b两个数的最小公倍常用ab/(a和b的最大公约数)，但在此题中，容易超过32位数据范围（计算ab时），故而计算最小公倍数采用a/(a和b的最大公共约数)*b
2、本题解决的是求任意多个数的最小公倍数

#include<iostream> 
using namespace std;
//寻找两个数的最小公倍数 
int lcm(int a,int b){
    int m,n,c,t;m=b;n=a;if(a<b){
    t=a;a=b;b=t;} c=a%b;//a,b的最大公约数是b while(c!=0){
    a=b;b=c;c=a%b;}return n/b*m;
}
int main(){
    int n,m;int result;cin>>n;for(int i=0;i<n;i++){
    cin>>m;int *num=new int[m];for(int i=0;i<m;i++){
    cin>>num[i];}if(m<2) cout<<num[0]<<endl;else{
    for(int i=0;i<m-1;i++){
    num[i+1]=lcm(num[i],num[i+1]);result=num[i+1];}cout<<result<<endl;}}return 0;
}

1021、Fibonacci Again

There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).
Input
Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).
Output
Print the word “yes” if 3 divide evenly into F(n).

Print the word “no” if not.
Sample Input

0
1
2
3
4
5

Sample output

no
no
yes
no
no
no

Code:
通过递推式子，判断所得结果能否被3整除
1、方法一使用递归算法，会出现超时问题
2、通过递归算法，发现2、6、10、14、18、22等均输出yes，找出规律

//方法一
#include<iostream>
using namespace std;
int f(int n){
    int result;if(n==0){
    result=7;}else if(n==1){
    result=11;}else{
    result=f(n-1)+f(n-2);}return result;
}
int main(){
    int n;while(cin>>n){
    if(f(n)%3==0){
    cout<<"yes"<<endl;}else{
    cout<<"no"<<endl;}}return 0;
} 

//方法二：
#include<iostream>
using namespace std;
int main(){
    int n;while(cin>>n){
    if((n+2)%4==0)cout<<"yes"<<endl;elsecout<<"no"<<endl;}return 0;
}

1028、Ignatius and the Princess III[母函数模板]

“Well, it seems the first problem is too easy. I will let you know how foolish you are later.” feng5166 says.

“The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+…+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that “4 = 3 + 1” and “4 = 1 + 3” is the same in this problem. Now, you do it!”
Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.
Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.
Sample Input

4
10
20

Sample Output

5
42
627

Code:
母函数——解决组合一类的问题
1、如当n=4时，计算多项式（1+x+x²+x³+x⁴)(1+x²+x⁴)(1+x³)(1+x⁴），x⁴的系数即为所求结果

#include<iostream>
using namespace std;
int main(){
    int n,a[121],b[121];//n[1,120] while(cin>>n){
    for(int i=0;i<=n;i++){
    a[i]=1;b[i]=0;}for(int l=2;l<n+1;l++){
    for(int i=0;i<=n;i++){
    for(int j=0;j+i<=n;j=j+l){
    b[i+j]=b[i+j]+a[i];}}for(int k=0;k<=n;k++){
    a[k]=b[k];b[k]=0;}}cout<<a[n]<<endl;} return 0;
}

1029、Ignatius and the Princess IV

“OK, you are not too bad, em… But you can never pass the next test.” feng5166 says.

“I will tell you an odd number N, and then N integers. There will be a special integer among them, you have to tell me which integer is the special one after I tell you all the integers.” feng5166 says.

“But what is the characteristic of the special integer?” Ignatius asks.

“The integer will appear at least (N+1)/2 times. If you can’t find the right integer, I will kill the Princess, and you will be my dinner, too. Hahahaha…” feng5166 says.

Can you find the special integer for Ignatius?
Input
The input contains several test cases. Each test case contains two lines. The first line consists of an odd integer N(1<=N<=999999) which indicate the number of the integers feng5166 will tell our hero. The second line contains the N integers. The input is terminated by the end of file.
Output
For each test case, you have to output only one line which contains the special number you have found.
Sample Input

5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1

Sample Output

3
5
1

Code
查找出现次数至少为（n+1)/2的数
1、利用sort()，排序后找出第（n+1）/2个数

#include<iostream>
#include<algorithm>
using namespace std;
int num[999999];
int main(){
    int n;while(cin>>n){
    for(int i=0;i<n;i++){
    cin>>num[i];}sort(num,num+n);cout<<num[(n+1)/2]<<endl;}return 0;
}