Calculation 2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 840 Accepted Submission(s): 371
Problem Description
Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.
Input
For each test case, there is a line containing a positive integer N(1 ≤ N ≤ 1000000000). A line containing a single 0 follows the last test case.
Output
For each test case, you should print the sum module 1000000007 in a line.
Sample Input
Sample Output
题目大意:给你一个N,求小于等于N的不互质的数的总和。
欧拉公式的引伸:小于或等于n的数中,与n互质的数的总和为:φ(x) * x / 2。(n>1)
所以:res = n*(n-1)/2-n - phi[x]*x/2。
主要考对欧拉公式和欧拉定理的推广和理解,不多说,代码。
链接:http://acm.hdu.edu.cn/showproblem.php?pid=3501
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
typedef long long LL;
int eular(LL n) //欧拉函数
{
int i, ans = n;
for(i = 2; i * i <= n; i++)
{
if(n%i == 0)
{
ans -= ans/i;
while(n%i == 0)
n /= i;
}
}
if(n > 1) ans -= ans/n;
return ans;
}
int main()
{
LL n, ans;
while(scanf("%I64d", &n), n)
{
ans = n * (n+1) / 2 - n; //总和
ans -= eular(n) * n / 2; //减去互质的总和公式
ans %= 1000000007; //再取模
printf("%I64d\n", ans);
}
return 0;
}
分享到:
相关推荐
毕设和企业适用springboot企业数据管理平台类及跨境电商管理平台源码+论文+视频
功能说明: 环境说明: 开发软件:VS 2017 (版本2017以上即可,不能低于2017) 数据库:SqlServer2008r2(数据库版本无限制,都可以导入) 开发模式:mvc。。。
labview程序代码参考学习使用,希望对你有所帮助。
毕设和企业适用springboot社交应用平台类及用户数据分析平台源码+论文+视频
大米外贸商城系统 简称damishop 完全开源版,只需做一种语言一键开启全球133中语言自动翻译功能,价格实现自动汇率转换,集成微信支付宝 paypal以及国外主流支付方式,自带文章博客系统。 软件架构 基于MVC+语言包模式,增加控制台,API导入产品方便对接其他系统(带json示例数据)。 使用要求 PHP7.4+ MYSQL5.6+ REDIS(可选) 安装方法 composer install 打开安装向导安装 http://您的域名/install 特色 1、缓存层增加时间与批量like删除 2、API产品导入方便对接其他系统 3、增加控制台命令行,命令行生成语言翻译包 4、后台一键开启自动翻译模式,支持全球133中语言,由于google代理翻译需要收费,这个功能需要付费。 5、可选购物车与ajax修改购物车产品 6、一键结算checkout 7、增加网站前台自定义路由 方便seo 更新日志 v3.9.7 集成鱼码支付接口,方便个人站长即使收款到账使用 v3.9.3 更新内容 1:增加ueditor与旧编辑器切换 2:增加可视化布局插
labview程序代码参考学习使用,希望对你有所帮助。
毕设和企业适用springboot生鲜鲜花类及生物识别平台源码+论文+视频.zip
毕设和企业适用springboot企业健康管理平台类及视觉识别平台源码+论文+视频.zip
毕设和企业适用springboot视频编辑类及餐饮管理平台源码+论文+视频.zip
labview程序代码参考学习使用,希望对你有所帮助。
毕设和企业适用springboot社区物业类及智能仓储平台源码+论文+视频
毕设和企业适用springboot企业知识管理平台类及人工智能医疗平台源码+论文+视频
毕设和企业适用springboot汽车电商类及新闻传播平台源码+论文+视频
毕设和企业适用springboot生鲜鲜花类及全渠道电商平台源码+论文+视频.zip
毕设和企业适用springboot企业数据智能分析平台类及投票平台源码+论文+视频
毕设和企业适用springboot全渠道电商平台类及人工智能客服平台源码+论文+视频
毕设和企业适用springboot企业云存储平台类及AI数据标注平台源码+论文+视频
毕设和企业适用springboot人工智能客服系统类及旅游规划平台源码+论文+视频
毕设和企业适用springboot社交电商类及环境监控平台源码+论文+视频
毕设和企业适用springboot生鲜鲜花类及大数据存储平台源码+论文+视频