首页 > ACM题库 > HDU-杭电 > hdu 2588 GCD-数论应用-[解题报告]C++
2014
02-10

hdu 2588 GCD-数论应用-[解题报告]C++

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

又一道欧拉函数题,题目要求小于等于n且与n的最大公约数大于等于m的所有数的个数

欧拉函数只能求出小于n且与n互质的所有数的个数,但是无法求出最大公约数是否大于m

但是 我们可以这样想 设a为大于等于m的n的一个约数,那么euler(n/a)表示的就是所有小于a与a互质的数的个数,设任一个数为x,那么这些数再乘以a就有gcd(n,x*a) = a;

所以我们可以想到答案为所有n大于等于m的约数ai的euler(n/ai)之和

但是还有一个问题 这些数是否会重复呢?答案是否定的

设a、b为两个不同的大于等于m的n的约数

假设存在重复 那么就有 a*x = b*y (x是小于等于n/a且与n/a互质的数,y是n/b的。。)

变形 得到 x*n/b = y*n/a 由于x和n/a互质 所以 x是y的约数(因为两边分解质因数的时候n/a不能分出x的约数 只能是y来分)

不妨设 y = kx(k>1)  则 n/b = k(n/a)

由于y和n/b互质 则kx和n/b互质 但是n/b有个k作为约数 所以他们有公约数k 这显然推出k = 1 于是产生a==b矛盾!

所以不会产生重复

最后注意一下 m=1的时候答案就是n 直接加结果貌似不对

贴段代码

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

解题转自:http://blog.csdn.net/xing89qs/article/details/8578422


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