[HDU 5608] function

Problem Description There is a function f(x),which is defined on the natural numbers set N,satisfies the following eqaution
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;
}