HDU 3501 Calculation 2
2024-09-21 06:26:14
题目大意:求小于n的与n不互质的数的和。
题解:首先欧拉函数可以求出小于n的与n互质的数的个数,然后我们可以发现这样一个性质,当x与n互质时,n-x与n互质,那么所有小于n与n互质的数总是可以两两配对使其和为n,这也就是为什么当n大于2时欧拉函数都是偶数,知道这一点后,就可以计算出小于n与n互质的数的和了,那么不互质的和只要用总和来减就可以了。
#include <cstdio>
typedef long long LL;
LL n,ans;
LL Eular(LL n){
LL ret=1;
for(int i=2;i*i<=n;i++){
if(n%i==0){
n/=i,ret*=(i-1);
while(n%i==0)n/=i,ret*=i;
}
}
if(n>1)ret*=(n-1);
return ret;
}
int main(){
while(~scanf("%lld",&n)&&n){
ans=n*(n+1)/2-n;
ans-=Eular(n)*n/2;
printf("%lld\n",ans%1000000007);
}return 0;
}
最新文章
- 如何利用Pre.im分发iOS测试包
- TCP 介绍
- Python中如何读取xml的数据
- Unity Editor not displaying Android textures properly
- sort()排序
- Copy an serializable object deeply
- 软件各种版本的含义!例如RC,M,GA等等
- postgresql 修改属性
- BZOJ 3680: 吊打XXX【模拟退火算法裸题学习,爬山算法学习】
- PageRank算法实现
- {黑掉这个盒子} \\ FluxCapacitor Write-Up
- UnDistracted for Mac(集中注意力辅助工具)破解版安装
- [svc]sort-uniq
- MDI窗体容器
- SpringMVC+Spring+mybatis项目从零开始--分布式项目结构搭建
- Visual Studio 2017 远程调试(Remote Debugger)应用
- Java基础(3)——变量
- Pylint 使用手册(正在努力翻译中)
- 用体渲染的方法在Unity中渲染云(18/4/4更新)
- FOR XML PATH 灵活运用