试题 算法提高 欧拉函数
【蓝桥杯---试题 算法提高 欧拉函数（数学）】资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
老师出了一道难题，小酱不会做，请你编个程序帮帮他，奖金一瓶酱油：
从1—n中有多少个数与n互质?
|||||╭══╮ ┌═════┐
╭╯让路║═║酱油专用车║
╰⊙═⊙╯ └══⊙═⊙═(坑爹的题面格式化，害得我用‘|’来代替空格，复制到记事本上看就变成正版的了)
输入格式
输入共一行，表示一个整数n。
输出格式
输出共一行，表示从1—n中与n互质的数的个数。
样例输入
30
样例输出
8
数据规模和约定
60%的数据≤10^6
100%的数据≤2*10^9
知识点：（欧拉公式）
文章图片
code：
#include
using namespace std;
typedef long long ll;
void f(ll n)
{
ll ans=n;
for(int i=2;
i*i<=n;
i++){
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0){//消除当前质因子
n/=i;
}
}
if(n==1)break;
}
if(n!=1){//n如果不为1说明n为素数，所以于其互质的有n-1个
ans=ans/n*(n-1);
}
printf("%lld",ans);
return ;
}int main()
{
ll n;
scanf("%lld",&n);
f(n);
return 0;
}
推荐阅读
- 算法|蓝桥云课 含2天数
- 31日打卡|蓝桥杯真题31日冲刺国一 | 每日题解报告 第六天
- 剑指offer|统计回文oj
- 备战蓝桥杯|【蓝桥python冲刺31天】——拿下数论，冲进国赛
- python|矩阵快速幂算法及相关应用（含python源码）
- JAVA|蓝桥杯动态规划这么好理解（）
- java|JAVA 打印菱形
- 蓝桥杯|JAVA 数组专题（韩顺平）
- java|java 逻辑运算符（韩顺平）