首页 > ACM题库 > HDU-杭电 > HDU 3875-Euclidean Algorithm[解题报告]HOJ
2015
04-13

HDU 3875-Euclidean Algorithm[解题报告]HOJ

Euclidean Algorithm

问题描述 :

wr recently learned the Euclidean algorithm to solve the greatest common divisor,then he realized that the algorithm can also be able to solve the least common multiple.In order to train the skill of code,he find a number p(1<=p<=2^25)and a number q(1<=q<=2^25) then he got n=p*q,he calculated a1=∑gcd(i, n) 1<=i <=n and a2= ∑lcm(i, n) 1<=i <=n,he wants to know if a2-a1 is the multiple of c(1<=c<=10^9)

输入:

The first line contains the number of scenarios.
Every scenario consists of a single line containing two integers n and c separated by a space.

输出:

The first line contains the number of scenarios.
Every scenario consists of a single line containing two integers n and c separated by a space.

样例输入:

2
6 100
4 2

样例输出:

no
yes

/* 功能Function Description:
   开发环境Environment:          DEV C++ 4.9.9.1
   技术特点Technique:
   版本Version:
   作者Author:               Myacing
   日期Date:                 20120723
   备注Notes:
*/
#include <stdio.h>
int main()
{
    int n, m, i, j, t, a[100000];
    while(1)
    {
         scanf("%d%d",&n,&m);
         if(n==0&&m==0)
         break;
         for(i=0;i<n;i++)
         scanf("%d",&a[i]);
         for(j=0;j<m;j++)  //这个冒泡其实不用完全比较完的,因为要是比较晚的话就要超时了 ,并且冒泡注意范围的判定 
         for(i=0;i<n-j-1;i++)
         {
             if(a[i]>a[i+1])
             {
                t=a[i];
                a[i]=a[i+1];
                a[i+1]=t;
             }
         }
         for(i=n-1;i>n-1-m;i--)
         {
                         if(i==n-1)
                         printf("%d",a[i]);
                         else
                         printf(" %d",a[i]);
         }
         printf("\n");
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/myacing/article/details/7800017


  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;