数論(反発原理)hdu-459-theボスon Mars
2461 ワード
タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=4059
タイトルの大意:
1つのnを与え,1~nにおけるnとの相互質の数の4乗の総和を求める.
問題解決の考え方:
反発原理、逆元、公式.
実は簡単な問題です.囧囧.
まず、1^4+2^4+…+n^4=n*(n+1)*(2 n+1)(3 n^2+3 n-1)/30を知る必要があります.30を割ると30を乗じた逆元に変換でき、30^(M-2)はフェマの小さな定理によってすぐに得ることができます.
まず1^4+2^4+...+n^4を求め,nと非互質を減算する. n=p 1^a 1*p 2^a 2...pn^an 反発原理を用いて,1つの素因数を含むすべてのnを超えない倍数を減算し,次いで2つの素因数を含むものを加算し,次いで3つの素因数を含むものを減算した.1つのdfsでできます.
コード:
http://acm.hdu.edu.cn/showproblem.php?pid=4059
タイトルの大意:
1つのnを与え,1~nにおけるnとの相互質の数の4乗の総和を求める.
問題解決の考え方:
反発原理、逆元、公式.
実は簡単な問題です.囧囧.
まず、1^4+2^4+…+n^4=n*(n+1)*(2 n+1)(3 n^2+3 n-1)/30を知る必要があります.30を割ると30を乗じた逆元に変換でき、30^(M-2)はフェマの小さな定理によってすぐに得ることができます.
まず1^4+2^4+...+n^4を求め,nと非互質を減算する. n=p 1^a 1*p 2^a 2...pn^an 反発原理を用いて,1つの素因数を含むすべてのnを超えない倍数を減算し,次いで2つの素因数を含むものを加算し,次いで3つの素因数を含むものを減算した.1つのdfsでできます.
コード:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define M 1000000007
using namespace std;
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
ll pp[10]; //10
ll cnt,n,sum,mm;
ll quick(ll a,ll b) // a^b mod M 30
{
ll res=1;
while(b)
{
if(b&1)
res=(res*a)%M;
a=(a*a)%M;
b>>=1;
}
return res;
}
ll Four(ll k) //1^4+2^4+...+n^4
{
return ((((k*(k+1))%M*(2*k+1))%M*((3*k*k%M+3*k-1)%M))%M*mm)%M;
}
void Cal(ll a,ll flag) // a n
{
ll k=n/a; //a^4+(2a)^4+(3a)^4+...(k*a)^4=a^4*(1^4+2^4+...+k^4)
ll res=1;
for(int i=1;i<=4;i++) // a
res=(res*a)%M;
res=(res*Four(k))%M; // 1~k
if(flag&1) //
sum=((sum-res)%M+M)%M;
else
sum=(sum+res)%M;
}
void dfs(ll la,ll pos,ll num) //la ,pos ,num
{
if(pos>cnt)
return ;
for(int i=pos;i<=cnt;i++)
{
Cal(la*pp[i],num); //
dfs(la*pp[i],i+1,num+1);
}
}
int main()
{
int t;
scanf("%d",&t);
mm=quick(30,M-2); //
while(t--)
{
scanf("%I64d",&n);
cnt=0;
ll nn=n;
sum=Four(n); //
for(int i=2;i*i<=nn;i++) // √n
{
if(nn%i==0)
{
pp[++cnt]=i;
while(nn%i==0)
nn/=i;
}
}
if(nn!=1)
pp[++cnt]=nn;
dfs(1,1,1);
printf("%I64d
",sum);
}
return 0;
}