C++ 数论相关题目(欧拉函数)

发布时间:2024年01月24日

欧拉函数

给定 n
个正整数 ai
,请你求出每个数的欧拉函数。

欧拉函数的定义
1~N
中与 N
互质的数的个数被称为欧拉函数,记为 ?(N)

若在算数基本定理中,N=pa11pa22…pamm
,则:
?(N)
= N×p1?1p1×p2?1p2×…×pm?1pm
输入格式
第一行包含整数 n

接下来 n
行,每行包含一个正整数 ai

输出格式
输出共 n
行,每行输出一个正整数 ai
的欧拉函数。

数据范围
1≤n≤100
,
1≤ai≤2×109
输入样例:
3
3
6
8
输出样例:
2
2
4
题解:主要是理解并记住公式。(欧拉函数证明)
在这里插入图片描述

#include <iostream>

using namespace std;

int n;

int main ()
{
    cin >> n;
    while(n -- )
    {
        int a;
        cin >> a;
        
        int res = a;
        for(int i = 2; i <= a / i; i ++ )
        {
            if(a % i == 0)
            {
                res = res / i * (i - 1);
                while(a % i == 0)
                    a /= i;
            }
        }
        if(a > 1) res = res / a * (a - 1);
        cout << res <<endl;
    }
    
    return 0;
}
文章来源:https://blog.csdn.net/qq_45281807/article/details/135830418
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。