【bzoj2705】[SDOI2012]Longge的问题 欧拉函数
2024-10-20 20:41:55
题目描述
Longge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数N,你需要求出∑gcd(i, N)(1<=i <=N)。
输入
一个整数,为N。
输出
一个整数,为所求的答案。
样例输入
6
样例输出
15
题解
欧拉函数
易得知满足gcd(n,x)==i的小于等于n的x的个数为phi(n/i),
并且欧拉函数可以在O(√n)的时间内快速求出。。
于是可以先求出所有n的因子,再用欧拉函数得出答案。
由于因子是成对出现的,所以因子并不需要枚举到n,只需枚举到√n。如果i是n的因子,那么n/i也是n的因子,注意此时i*i==n不能算进答案内。
#include <cstdio>
typedef long long ll;
ll phi(ll x)
{
ll ans = x , t = x , i;
for(i = 2 ; i * i <= x ; i ++ )
{
if(t % i == 0) ans = ans * (i - 1) / i;
while(t % i == 0) t /= i;
}
if(t > 1) ans = ans * (t - 1) / t;
return ans;
}
int main()
{
ll n , i , ans = 0;
scanf("%lld" , &n);
for(i = 1 ; i * i <= n ; i ++ )
{
if(n % i == 0)
{
ans += i * phi(n / i);
if(i * i < n) ans += (n / i) * phi(i);
}
}
printf("%lld\n" , ans);
return 0;
}
最新文章
- 如何生成报告来枚举出整个sharepoint环境中的每个页面所使用的所有webpart
- Objective-C中把数组中字典中的数据转换成URL
- Validation-jQuery表单验证插件使用方法
- 【WebGoat习题解析】AJAX Security->;Insecure Client Storage
- alarm
- unix 文件属性
- Android自定义控件(一)——开关控件
- 兼容各个浏览器的H.264播放: H.264+HTML5+FLOWPLAYER+WOWZA+RMTP
- Crystal Report分組中的序號重新遞增
- HotelIInventory项目小结
- Linux cronolog
- 跟随上次的socket sever,追加Tcplistener、Httplistener的server
- codeforge免费下载账号 积分账号 共享账号
- AngularJS学习之旅—AngularJS Select(十)
- 《转》studio界面、快捷键
- c# nginx 配置
- ural Ambitious Experiment 树状数组
- MP1593 RT8272 ACT4070 制作的DC-DC稳压电源
- wifi免密码登录认证流程
- JAVA中return的用法
热门文章
- django项目创建requirements.txt文件
- ASP.NET HttpHandler加水印
- 【c学习-12】
- ECSHOP和SHOPEX快递单号查询顺丰插件V8.6专版
- 百度收录检测并主动推送API(实时 mip推送通用)
- 使用mysql5.7版本数据库需要注意的地方/持续更新
- 解决Pycharm无法使用已经安装Selenium的问题
- python 用装饰器写登录
- Preparing Cities for Robot Cars【城市准备迎接自动驾驶汽车】
- 基于Ubuntu Server 16.04 LTS版本安装和部署Django之(三):设置上传文件夹权限(这里测试用完全共享)