3512: DZY Loves Math IV
Time Limit: 15 Sec Memory Limit: 128 MB
Submit: 442 Solved: 219
[Submit][Status][Discuss]
Description
給定n,m,求
模10^9+7的值。
Input
僅一行,兩個整數n,m。
Output
僅一行答案。
Sample Input
100000 1000000000
Sample Output
857275582
資料規模:
1<=n<=10^5,1<=m<=10^9,本題共4組資料。
HINT
Source
By Jc 鳴謝杜教
【分析】
公式恐懼症
還有…DZY是誰
【代碼】
//IV
#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100000
#define ll long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int mod=e9+;
const int mxn=;
ll ans;
int n,m;
bool vis[mxn];
map <ll,int> A,B;
int k[mxn],phi[mxn],pri[mxn],sum[mxn];
inline void init()
{
int i,j;
phi[]=k[]=;
fo(i,,N)
{
if(!vis[i]) pri[++pri[]]=i,phi[i]=i-,k[i]=;
for(j=;j<=pri[] && i*pri[j]<=N;j++)
{
vis[i*pri[j]]=;
if(i%pri[j]==)
{
phi[i*pri[j]]=phi[i]*pri[j];
k[i*pri[j]]=k[i]*pri[j];
break;
}
k[i*pri[j]]=k[i];
phi[i*pri[j]]=phi[i]*(pri[j]-);
}
}
fo(i,,N) sum[i]=(phi[i]+sum[i-])%mod;
}
inline int P(int n)
{
if(n<=N) return sum[n];
if(B.count(n)) return B[n];
ll res=(ll)n*(n+)/%mod;
for(int i=,last=;i<=n;i=last+)
{
last=n/(n/i);
res=(res-(ll)(last-i+)*P(n/i))%mod;
}
return B[n]=(res+mod)%mod;
}
inline ll S(int n,int m)
{
ll res=;
if(!m) return ;
if(A.count((ll)n*mod+m)) return A[(ll)n*mod+m];
if(n==) return A[(ll)n*mod+m]=P(m);
for(int i=;i*i<=n;i++)
if(n%i==)
{
res=(res+(ll)phi[n/i]*S(i,m/i)%mod)%mod;
if(i*i!=n)
res=(res+(ll)phi[i]*S(n/i,m/(n/i))%mod)%mod;
}
return A[(ll)n*mod+m]=res;
}
int main()
{
init();
int i,j;
scanf("%d%d",&n,&m);
fo(i,,n)
ans=(ans+(ll)k[i]*S(i/k[i],m)%mod)%mod;
printf("%lld\n",ans);
return ;
}