poj2478(欧拉函数)
2024-09-27 19:58:42
题目链接:https://vjudge.net/problem/POJ-2478
题意:给定n,输出集合中元素的数量,集合中的元素为最简小于1的分数,分子分母均属于[1,n-1]。
思路:理清题意后就是输入n,输出[1,n]区间所有数的欧拉函数之和。要注意结果会超出int范围。
AC代码:
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=; int eu[maxn],n;
LL sum[maxn]; void eular(){
for(int i=;i<=;++i){
if(!eu[i])
for(int j=i;j<=;j+=i){
if(!eu[j]) eu[j]=j;
eu[j]=eu[j]/i*(i-);
}
sum[i]=sum[i-]+eu[i];
}
} int main(){
eular();
while(scanf("%d",&n),n)
printf("%lld\n",sum[n]);
return ;
}
最新文章
- Session: 防止用户多次登陆
- Powershell的内置变量
- POJ 1966 Cable TV Network(顶点连通度的求解)
- GOOGLE 离线完整安装包下载地址
- IE6 IE7: div中table宽度100%导致的宽度问题
- express源码剖析2
- MySQL 连接
- Request url 各种属性值
- poj 1458 Common Subsequence(区间dp)
- POJ 2135 最小费用最大流
- mysql解压包安装教程
- 【python】【logging】python日志模块logging常用功能
- python 【pandas】账号、银行卡号、身份证号导出文件后以科学计数法显示问题解决
- Mybatis连接配置文件详解
- Python判断字符集
- 运行代码时报linker command failed with exit code 1 错误
- MySQL ";replace into"; 的坑以及insert相关操作
- Mac安装软件时提示已损坏的解决方法
- 第五章 MyEclipse配置hadoop开发环境
- Redis介绍与安装
热门文章
- 计算机网络(二),TCP/IP四层模型常见协议
- 2018 计蒜之道-初赛 第一场 A-百度无人车
- unittest详解(二) 跳过用例的执行(skip)
- 实体字符转换,同样变量密码加盐MD5后生成的加密字符串不同解决办法 (原)
- R_Studio(学生成绩)对数据缺失值md.pattern()、异常值分析(箱线图)
- 暂时跳过的Leetcode题目
- 第六周学习总结&;第四次实验报告
- 2018092609-2 选题 Scrum立会报告+燃尽图 04
- 清明 DAY 4
- leetcode 328 奇偶链表