[HDU 5608] function
N2−3N+2=∑d|Nf(d) N 2 − 3 N + 2 = ∑ d | N f ( d )
calulate ∑ni=1f(i) mod 109+7 ∑ i = 1 n f ( i ) m o d 10 9 + 7 .
Input the first line contains a positive integer T,means the number of the test cases.
next T lines there is a number N
T≤500,N≤109 T ≤ 500 , N ≤ 10 9
only 5 test cases has N>106.
Output Tlines,each line contains a number,means the answer to the i-th test case.
Sample Input 1 3
Sample Output 2
12−3∗1+2=f(1)=0 1 2 − 3 ∗ 1 + 2 = f ( 1 ) = 0 22−3∗2+2=f(2)+f(1)=0−>f(2)=0 2 2 − 3 ∗ 2 + 2 = f ( 2 ) + f ( 1 ) = 0 − > f ( 2 ) = 0 32−3∗3+2=f(3)+f(1)=2−>f(3)=2 3 2 − 3 ∗ 3 + 2 = f ( 3 ) + f ( 1 ) = 2 − > f ( 3 ) = 2 f(1)+f(2)+f(3)=2 f ( 1 ) + f ( 2 ) + f ( 3 ) = 2
이전의 작법은 순기억화였지만, 시간이 초과되었구나.그래서 역시 두교체처럼 전 1000000의 ans를 미리 처리한 다음에 귀속 집약화하면 된다.코드:
#include
#include
#include
#include
#include
#include
#define maxx 1000005
#define ll long long
using namespace std;
const int mod=1000000007;
ll ans[maxx];
map M;
ll inv=333333336;
void init()
{
for(int i=1;i1)*(i-2)%mod;
for(int i=1;ifor(int j=i+i;jfor(int i=1;i1])%mod;
}
ll work(ll x)
{
if(xreturn ans[x];
if(M[x])return M[x];
ll res=x*(x-1)%mod*(x-2)%mod*inv%mod;
for(ll i=2,last;i<=x;i=last+1)
{
last=x/(x/i);
res=(res-(last-i+1)*work(x/i)%mod)%mod;
}
res=(res+mod)%mod;
M[x]=res;
return res;
}
ll p(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int main()
{
//cout<
init();
ans[1]=0;
int t;
cin>>t;
while(t--)
{
ll n;
scanf("%lld",&n);
printf("%lld
",work(n));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU 5608] functionProblem Description There is a function f(x),which is defined on the natural numbers set N,satisfies the following eqaut...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.