首页 > 代码库 > HDU 3501-Calculation 2(欧拉函数)
HDU 3501-Calculation 2(欧拉函数)
题目链接:传送门
题意:求区间 [1,n-1] 内与n不互质的数的和。
欧拉函数性质: 区间 [1,n-1] 内与n互质的数的和为 phi(n)*n/2 用总和 n*(n-1)/2 (等差数列和) 减去 phi(n)*n/2 即为所求答案。
欧拉函数版:
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 360 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair<int,int> #define ull unsigned long long #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; ll phi(ll n) { ll ans=n,m=(ll)sqrt(n+0.5); for(ll i=2;i<=m;i++) if(n%i==0) { ans=ans/i*(i-1); while(n%i==0)n/=i; } if(n>1)ans=ans/n*(n-1); return ans; } int main() { ll n; while(~scanf("%lld",&n)&&n) { if(n==1) { puts("0"); continue; } ll sum=(n-1)*n/2; ll ans=phi(n)*n/2; printf("%lld\n",(sum-ans)%Mod); } return 0; }
容斥版:(两种都跑了200MS+ 不知道人家怎么0ms过的)
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 360 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair<int,int> #define ull unsigned long long #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; ll fac[maxn],tot,ans; void div(ll n) { tot=0; ll m=(ll)sqrt(n+0.5); for(ll i=2;i<=m;i++) { if(n%i==0) { fac[tot++]=i; while(n%i==0)n/=i; } } if(n>1)fac[tot++]=n; } void dfs(ll num,ll s,ll r,ll n) { if(num==tot) { if(s&1)ans-=n/r; else ans+=n/r; return ; } dfs(num+1,s,r,n); dfs(num+1,s+1,r*fac[num],n); } int main() { ll n; while(~scanf("%lld",&n)&&n) { if(n==1) { puts("0"); continue; } div(n);ans=0;dfs(0,0,1,n); ll sum=(n-1)*n/2; ll tem=ans*n/2; printf("%lld\n",(sum-tem)%Mod); } return 0; }
HDU 3501-Calculation 2(欧拉函数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。