HDU 3501 Calculation 2 ——Dirichlet积
2024-08-26 00:55:55
【题目分析】
卷积太有趣了。
最终得出结论,互质数和为n*phi(n)/2即可。
计算(n*(n+1)/2-n-n*phi(n)/2)%md,用反正法即可证明。
【代码】
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <map> #include <set> #include <queue> #include <string> #include <iostream> #include <algorithm> using namespace std; #define maxn 500005 #define md 1000000007 #define ll long long #define inf 0x3f3f3f3f #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) void Finout() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); #endif } int Getint() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') x=x*10+ch-'0'; return x*f; } ll n; ll phi(ll x) { ll t=x,upp=sqrt(x); F(i,2,upp) { if (x%i==0) {t/=i;t*=i-1;} while (x%i==0) x/=i; } if (x>1) t/=x,t*=x-1; return t; } int main() { Finout(); while (scanf("%lld",&n)&&n) cout<<(n*(n+1)/2-n-n*phi(n)/2)%md<<endl; }
最新文章
- C++ 定义全局数组
- MIT License
- 如何对具有端点加密功能的LINE进行取证
- DICOM医学图形处理:storescp.exe与storescu.exe源码剖析,学习C-STORE请求(续)
- P1026 犁田机器人
- Dictionary<;实体,List<;实体>;>;的比较
- window7 输入什么命令可以快速打开服务管理?? 虚拟机设置了NAT网络连接方式,还是无法上网?
- c++ containers
- EasyUI 扩展自己定义EasyUI校验规则 验证规则(经常使用的)
- 错排-HDU 2049 递推的应用
- C# 动态加载卸载 DLL
- [Kubernetes]PV,PVC,StorageClass之间的关系详解
- [模板] 回文树/回文自动机 &;&; BZOJ3676:[Apio2014]回文串
- BZOJ4437 : [Cerc2015]Looping Labyrinth
- 请找出至少一个由递推关系 a(i) = a(i – 1) + a(i – 2) 生成的数列,使得当 n 趋于 (√5+1)/2的数列
- POJ2478(SummerTrainingDay04-E 欧拉函数)
- JavaScript语法详解:if语句&;for循环&;函数
- 使用Python的turtle(海龟)模块画图
- 【C】——C利用回调函数实现多态
- free详解