题目训练（包含容斥定理）（密码hpuacm）：https://vjudge.net/contest/240973#overview

主要有以下内容：

1. 质因子分解

2. 质因子个数

3. 求数N的所有因子之和

 

4. 算术基本定理角度看GCD和LCM

代码实现：

质因数分解，个数统计，求和

#include <cstdio>
#include <math.h>
#include <map>
using namespace std;

map<int, int> ans;
int sz;

map<int,int> f( int n )
{
	map<int,int> ans;
	int temp = sqrt(n);
	for( int i=2; i<=temp; i++ )
	{
		while( n%i == 0 )
		{
			ans[i]++;
			n /= i;
		}
	}
	if( n != 1 )
		ans[n] = 1;
	return ans;
}
int main()
{
	int n ;
    int cnt = 1;    // 全体正因数个数
    int sum = 1;    // 全体正因数的和
	scanf("%d", &n );
	ans = f(n);

	map<int,int> :: iterator it;
	for( it = ans.begin(); it != ans.end(); it++ )
	{
		printf("%d -> %d\n", it->first, it->second );   // 底数和指数
        cnt  = cnt * (it->second+1);
        sum *= (pow(it->first, it->second+1) - 1)/(it->first - 1);

	}
    printf("cnt = %d\n", cnt );
    printf("sum = %d\n", sum );


	return 0;
}

算术基本定理角度求GCD和LCM的代码实现

#include <bits/stdc++.h>
using namespace std;

int prime[1000000] = { 1, 1 };
vector<int> ve;
int sz;

map<int,int> f( int n )
{
    map<int,int> ans;
    int temp = sqrt(n);
    for( int i=0; ve[i]*ve[i] <= n && i<sz ; i++ )
    {
        ans[ve[i]];
        while( n%ve[i] == 0 )
        {
            ans[ve[i]] ++;
            n /= ve[i];
        }
    }
    if( n != 1 )
        ans[n] = 1;
    return ans;
}
int main()
{
    /*提前预处理1e6以内的素数，并将素数放入一个新的数组内*/
    for( int i=2; i<1005; i++ )
    {
        if( !prime[i] )
            for( int j=i+i; j<1000000; j += i )
                prime[j] = 1;
    }
    for( int i=0; i<1000000; i++ )
        if( !prime[i] )
            ve.push_back(i);

    map<int,int> ans1;
    map<int,int> ans2;
    int n, m;
    sz = ve.size();

    while( scanf("%d%d", &n, &m ) != EOF )
    {
        ans1.clear();
        ans2.clear();
        double gcd = 1;    // 这里定义为double
        double lcm = 1;
        ans1 = f(n);
        ans2 = f(m);
        map<int,int> :: iterator it;
        // 下面这两个for循环是输出产生的两个map
        for( it = ans1.begin(); it != ans1.end(); it ++ )
        {
            printf("%d %d\n", it->first, it->second );
        }
        printf("-----------------\n");
        for( it = ans2.begin(); it != ans2.end(); it ++ )
        {
            printf("%d %d\n", it->first, it->second );
        }
        
        if( ans1.size() > ans2.size() )
        {
            for( it = ans1.begin(); it != ans1.end(); it++ )
            {
                // 这里解释为什么定义为double， 如果定义为整型，因为pow()的返回值类型是double，所以会造成计算结果的错误
                // 我用codeblocks编译器就会因为这个原因造成结果错误
                // 当然用不同的计算机或者不同的编译器产生的结果不同也是有可能的
                gcd *= pow( it->first, min(it->second, ans2[it->first]) );
                lcm *= pow( it->first, max(it->second, ans2[it->first]) );
            }
        }
        else
        {
            for( it = ans2.begin(); it != ans2.end(); it++ )
            {
                gcd *= pow( it->first, min(it->second, ans1[it->first]) );
                lcm *= pow( it->first, max(it->second, ans1[it->first]) );
            }
        }

        printf("gcd = %.0f\n", gcd );
        printf("lcm = %.0f\n", lcm );

    }

    return 0;
}

欧拉函数:

对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。

对于一个正整数N的素数幂分解N=P1^q1*P2^q2*...*Pn^qn.

Euler函数表达通式：euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),或者φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),

其中p1,p2……pn为x的所有素因数，x是不为0的整数。

euler(1)=1（唯一和1互质的数就是1本身）。 
欧拉公式的延伸：一个数的所有质因子之和是euler(n)*n/2。

#include <cstdio>
#include <math.h>
using namespace std;
typedef long long LL;

LL oula( LL n )
{
    LL ans = n;
    int t = sqrt(n);
    for( int i=2;  i <= t; i++ )
    {
        if( n%i == 0 )
        {
            ans = ans / i *(i-1);
            while( n%i ==0 )
                n = n / i;
        }
    }
    if( n != 1 )
        ans = ans/n * (n-1);
    return ans;
}

int main()
{
    LL n;

    while( scanf("%lld", &n ), n )
    {
        LL ans;
        ans = oula(n);
        printf("%lld\n", ans );
    }

    return 0;
}