2015
04-13

# 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;
}


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;