2014
02-10

GCD

The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6.
(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem:
Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.

The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.

The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.

3
1 1
10 2
10000 72

1
6
260

http://acm.hdu.edu.cn/showproblem.php?pid=2588

#include <string.h>
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int euler(int n){
int temp = n;
int sq_n = sqrt(n+0.5);
int ans = n;
for(int i = 2;i<=sq_n;i++){
if(n%i==0){
ans = ans/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) ans = ans/n*(n-1);
return ans;
}

int main(void){
//freopen("","r",stdin);
int t;
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d %d",&n,&m);
if(m==1){
printf("%d\n",n);
continue;
}
int ans = 0;
int sq_n = sqrt(n+0.5);
for(int i = 2;i<=sq_n;i++){
if(n%i==0){
if(i>=m) ans+=euler(n/i);
if(n/i>=m) ans+=euler(i);
}
}
if(n!=1&&sq_n*sq_n==n&&sq_n>=m) ans-=euler(sq_n);
printf("%d\n",ans+1);
}
}

1. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。