杭电ACM基础题（1339、1393、1395、1397、1405、1406、1407）

1339、A Simple Task[n=o*2^p]

Given a positive integer n and the odd integer o and the nonnegative integer p such that n = o2^p.

Example

For n = 24, o = 3 and p = 3.

Task

Write a program which for each data set:

reads a positive integer n,

computes the odd integer o and the nonnegative integer p such that n = o2^p,

writes the result.

Input
The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 10. The data sets follow.

Each data set consists of exactly one line containing exactly one integer n, 1 <= n <= 10^6.

Output
The output should consists of exactly d lines, one line for each data set.

Line i, 1 <= i <= d, corresponds to the i-th input and should contain two integers o and p separated by a single space such that n = o2^p.
Sample Input

1
24

Sample Output

3 3 

Code
给定n，求o和p,n=o*2^p，其中n为正整数,o为奇数,p为 非负数

//n=o*2^p，其中n为正整数,o为奇数,p为 非负数
#include<iostream>
#include<cmath>
using namespace std;
int yinshu[1000000];
//判断一个数是否为奇数 
int isOdd(int n){
    if(n%2==0)return 0;elsereturn 1;
} 
int main(){
    int d;cin>>d;while(d--){
    int n;cin>>n;//寻找n的因数int j=0;for(int i=1;i<=sqrt(n);i++){
    if(n%i==0){
    yinshu[j++]=i;yinshu[j++]=n/i;}}for(int k=0;k<j-1;k+=2){
    float a=yinshu[k];float b=yinshu[k+1];float c=log(b)/log(2);float d=log(a)/log(2);if(isOdd(a)==1&&int(c)==c||isOdd(b)==1&&int(d)==d){
    //判断一个数是否为整数if(isOdd(a)==1&&int(c)==c){
    cout<<int(a)<<" "<<int(c)<<endl;}    else{
    cout<<int(b)<<" "<<int(d)<<endl;}}}}
} 

1393、Weird Clock[给定s和d,判断至少需要几枚硬币使得分针转回0 ]

A weird clock marked from 0 to 59 has only a minute hand. It won’t move until a special coin is thrown into its box. There are different kinds of coins as your options. However once you make your choice, you cannot use any other kind. There are infinite number of coins of each kind, each marked with a number d ( 1 <= d <= 1000 ), meaning that this coin will make the minute hand move d times clockwise the current time. For example, if the current time is 45, and d = 2. Then the minute hand will move clockwise 90 minutes and will be pointing to 15.

Now you are given the initial time s ( 1 <= s <= 59 ) and the coin’s type d. Write a program to find the minimum number of d-coins needed to turn the minute hand back to 0.
Input
There are several tests. Each test occupies a line containing two positive integers s and d.

The input is finished by a line containing 0 0.
Output
For each test print in a single line the minimum number of coins needed. If it is impossible to turn the hand back to 0, output “Impossible”.
Sample Input

30 1
0 0

Sample Output

1

Code:
s代表当前指向的分钟数，每枚都标有数字d（1<=d<=1000），即该枚硬币使得分针按当前时间顺时针方向移动d倍
给定s和d,判断至少需要几枚硬币使得分针转回0

//s代表当前指向的分钟数，每枚都标有数字d（1<=d<=1000），即该枚硬币使得分针按当前时间顺时针方向移动d倍 
//给定s和d,判断至少需要几枚硬币使得分针转回0 
#include<iostream>
using namespace std;
int main(){
    int s,d;//s代表当前指向的分钟[1,59] ,d代表硬币类型[1,1000] while(cin>>s>>d){
    if(s==0&&d==0){
    return 0;}int m=(s+s*d)%60,i; //最多60次 for(i=1;i<=60;i++){
    if(m==0){
      break;}m=(m+m*d)%60;//每次m的值是变化的，即其起始位置是在改变的 }if(i<=60){
    cout<<i<<endl;}else{
    cout<<"Impossible"<<endl;}}

1395、2^x mod n = 1[取模运算]

Give a number n, find the minimum x(x>0) that satisfies 2^x mod n = 1.
Input
One positive integer on each line, the value of n.
Output
If the minimum x exists, print a line with 2^x mod n = 1.

Print 2^? mod n = 1 otherwise.

You should replace x and n with specific numbers.
Sample Input

2
5

Sample Output

2^? mod 2 = 1
2^4 mod 5 = 1

Code
2^x mod n=1,给定n，求使得其成立的x的最小值

//2^x mod n=1,给定n，求使得其成立的x的最小值
#include<iostream>
using namespace std;
int main(){
    int n;while(cin>>n){
    //n和2互质 int m=n;//n有2这个因数或者n为1时，不存在x if(n%2==0||n==1){
    cout<<"2^? mod "<<m<<" = 1"<<endl;}//否则存在x else{
    int a=1;for(int i=1;;i++){
    a=a*2%n;//pow(2,i)%n会超时 if(a==1){
    cout<<"2^"<<i<<" mod "<<m<<" = 1"<<endl;break;}}}}
} 

1397、Goldbach’s Conjecture[哥德巴赫猜想–n=p1+p2(素数打表)]

Goldbach’s Conjecture: For any even number n greater than or equal to 4, there exists at least one pair of prime numbers p1 and p2 such that n = p1 + p2.
This conjecture has not been proved nor refused yet. No one is sure whether this conjecture actually holds. However, one can find such a pair of prime numbers, if any, for a given even number. The problem here is to write a program that reports the number of all the pairs of prime numbers satisfying the condition in the conjecture for a given even number.

A sequence of even numbers is given as input. Corresponding to each number, the program should output the number of pairs mentioned above. Notice that we are interested in the number of essentially different pairs and therefore you should not count (p1, p2) and (p2, p1) separately as two different pairs.
Input
An integer is given in each input line. You may assume that each integer is even, and is greater than or equal to 4 and less than 2^15. The end of the input is indicated by a number 0.
Output
Each output line should contain an integer number. No other characters should appear in the output.
Sample Input

6
110
12
0

Sample Output

1
2
1

Code:
哥德巴赫猜想：对于任意一个大于4的偶数n，至少存在一个质数对(p1,p2)，使得n=p1+p2成立
利用素数打表

//哥德巴赫猜想：对于任意一个大于4的偶数n，至少存在一个质数对(p1,p2)，使得n=p1+p2成立 
//给出n，判断使得n=p1+p2成立的值有几对
//方法一：遍历并逐步判断两个数是不是素数，超时 
//方法二：利用素数打表法 
#include<iostream>
#include<cmath>
using namespace std;
int prime[32768]={
    0};
int main(){
    int n;//[4,2^15]//打表，标记4-32768之间的合数 for(int j=2;j<32769;j++){
    for(int k=2;j*k<32769;k++){
    prime[j*k]=1;//将合数对应的位置置为1 }}while(cin>>n){
    if(n==0) return 0;int a,b,count=0;for(int i=2;i<=n/2;i++){
    a=i;b=n-a;if(prime[a]==0&&prime[b]==0){
    count++;} }cout<<count<<endl;} 
} /* 方法一：这种方式会出现超时 //判断是否为质数的函数 int isPrime(int n){for(int i=2;i<=sqrt(n);i++){if(n%i==0)return 0;}return 1; }int main(){int n;//[4,2^15]while(cin>>n){if(n==0) return 0;int a,b,count=0;for(int i=2;i<=n/2;i++){a=i;b=n-a;if(isPrime(a)==1&&isPrime(b)==1){count++;} }cout<<count<<endl;} } */

1405、The Last Practice[将正数分解为一些质数的组合 如60：2 2 3 1 5 1 即60=2²*3¹*5¹]

Tomorrow is contest day, Are you all ready?
We have been training for 45 days, and all guys must be tired.But , you are so lucky comparing with many excellent boys who have no chance to attend the Province-Final.

Now, your task is relaxing yourself and making the last practice. I guess that at least there are 2 problems which are easier than this problem.
what does this problem describe?
Give you a positive integer, please split it to some prime numbers, and you can got it through sample input and sample output.
Input
Input file contains multiple test case, each case consists of a positive integer n(1<n<65536), one per line. a negative terminates the input, and it should not to be processed
Output
For each test case you should output its factor as sample output (prime factor must come forth ascending ), there is a blank line between outputs.
Sample Input

60
12
-1

Sample Output

Case 1.
2 2 3 1 5 1Case 2.
2 2 3 1

Code:
将正数分解为一些质数的组合 如60：2 2 3 1 5 1 即60=2²*3¹*5¹

//将正数分解为一些质数的组合 如60：2 2 3 1 5 1 即60=2^2*3^1*5^1#include<iostream>using namespace std;int main(){
    int n,t=0;//(1,65536)while(cin>>n){
    if(n<0) return 0;t++;if(t>1){
    cout<<endl; //注意格式问题，结果之间有一个空格}cout<<"Case "<<t<<"."<<endl;//输出Case 1.for(int i=2;i<=n;i++){
    int count=0;bool flag=false;//计算n可以被i整除的个数 while(n%i==0){
    count++;n=n/i;flag=true;    }if(flag==true){
    cout<<i<<" "<<count<<" ";}}cout<<endl;}} 

1406、完数[寻找给定区间完数的个数]

完数的定义：如果一个大于1的正整数的所有因子之和等于它的本身，则称这个数是完数，比如6，28都是完数：6=1+2+3；28=1+2+4+7+14。

本题的任务是判断两个正整数之间完数的个数。
Input
输入数据包含多行，第一行是一个正整数n，表示测试实例的个数，然后就是n个测试实例，每个实例占一行，由两个正整数num1和num2组成,(1<num1,num2<10000) 。
Output
对于每组测试数据，请输出num1和num2之间（包括num1和num2）存在的完数个数。
Sample Input

2
2 5
5 7

Sample Output

0
1

Code:
完数：如果一个大于1的正整数的所有因子之和等于它本身，则称这个数是完数
判断两个正整数之间完数的个数

//完数：如果一个大于1的正整数的所有因子之和等于它本身，则称这个数是完数
//判断两个正整数之间完数的个数
#include<iostream>
using namespace std;
int main(){
    int n;cin>>n;//测试实例的个数 while(n--){
    int num1,num2;//判断num1和num2之间完数的个数 (1,10000)cin>>num1>>num2;//num1可能大于num2if(num1>num2){
    int temp;temp=num2;num2=num1;num1=temp;} int count=0;for(int i=num1;i<=num2;i++){
    int sum=0;for(int j=1;j<i;j++){
    if(i%j==0)sum=sum+j;} if(sum==i){
    count++;}}cout<<count<<endl;}
} 

1407、测试你是否和LTC水平一样高[满足方程x²+y²+z²= num的一个正整数解（x,y,x）的值]

大家提到LTC都佩服的不行，不过，如果竞赛只有这一个题目，我敢保证你和他绝对在一个水平线上！
你的任务是：
计算方程x²+y²+z²= num的一个正整数解。
Input
输入数据包含多个测试实例，每个实例占一行，仅仅包含一个小于等于10000的正整数num。
Output
对于每组测试数据，请按照x,y,z递增的顺序输出它的一个最小正整数解，每个实例的输出占一行，题目保证所有测试数据都有解。
Sample Input

3

Sample Output

1 1 1

Code
计算方程x²+y²+z²= num的一个正整数解。
给定num,输出满足条件的x,y,z (按递增的顺序输出)

//计算方程x^2+y^2+z^2= num的一个正整数解。
//给定num,输出满足条件的x,y,z 
#include<iostream>
using namespace std;
int main(){
    int num;//(1,10000]while(cin>>num){
    int flag=0;//三重循环 for(int i=1;i*i<=num;i++){
    for(int j=1;j*j<=num;j++){
    for(int k=1;k*k<=num;k++){
    if((i*i)+(j*j)+(k*k)==num){
    cout<<i<<" "<<j<<" "<<k<<endl;flag=1;break;}}if(flag==1)break;}if(flag==1)break;}} 
}