BZOJ 3512: DZY Loves Math IV

Description

給定n,m，求 ∑ni=1∑mj=1φ(i∗j) mod 1e9+7

n<=100,000,m<=1,000,000,000

Solution

以為這題是之前那道多校的原題，高興地去刷了，然後，兩天過去了。。

n 那麼小顯然暴力枚舉即可

同樣的，我們定義sum(n,m)表示 ∑mi=1φ(i∗n)

然而這裡并不是 free square number

不要緊，顯然如果有個因數 p 有>1的幂，則 sum(n,m)=pαs−1sum(n/(pαs−1))

那麼一開始我們來一發質因數分解即可

然後同樣的， sum(n,m)=φ(p)∗sum(np,m)+sum(n,⌊mp⌋)

然後突然發現 m TM那麼大。。遞歸結尾傳回什麼。。

暴力搞肯定不行了，突然想到有種東西叫杜教篩

趕快拿起來研究了一下

就然我們來推導一下φ的字首和 ϕ 吧

ϕ(n)=∑1=1nφ(i)

又 ∑d|iφ(d)=n

=>φ(n)=n−∑d|n,d<nφ(d)

帶入原式可得

ϕ(n)=∑i=1ni−∑d|i,d<iφ(d)

=n∗(n+1)2−∑d|i,d<iφ(d)

換一下枚舉順序，枚舉i/d可得

ϕ(n)=n∗(n+1)2−∑i=2n∑i=1⌊ni⌋

=n∗(n+1)2−∑i=2nϕ(⌊ni⌋)

網上有個小哥蠻逗，他杜教篩的時候暴力for後面的東西，然後吐槽說常數有點大。。

事實上大家都會按值域搞一發即可

複雜度懶得證明，直接拿來用吧如果預處理前面的項 O(n23)

接下來是精髓，卡常數的部分

照理說這樣已經可以搞出來了，然而我在常數的坑裡徘徊了n久

一開始我在sum的時候套了個map，然後MLE了5次(當然那時樣例跑了20S+)

後來發現去掉map不僅時間變成了10S-而且不會MLE了。。

然後我在杜教篩的時候記搜中把map用手寫hash_table，又快了2S

現在的時間變成了8S整

我從網上随手拔了個AC代碼，親測7.6S，交一發，A了。。

于是我就各種不爽。

我在篩素數的時候把每個數字的最大因數給篩出來，然後看似可以省掉一個 n√ ?然而親測沒有效果。。

為什麼那個代碼同樣在求sum的時候套了個map，為什麼不好會MLE,而且可以跑到7.6S，遙(gui)遙(ce)領(ping)先(qi)

我再三反思，一定是輾轉相除的次數太多了，調用遞歸的次數太多了。。

完了多半是廢了。。

這時候我突然發現一開始的那個帶進去算sum的東西因為已經因式分解了，是以值域很窄？

無腦套了個記憶化

跑出了3S驚人的速度！！！

欣慰地笑了，感覺自己可以卡世界上一切常數了

Code

/**************************************************************
    Problem: 3512
    User: bblss123
    Language: C++
    Result: Accepted
    Time:8292 ms
    Memory:91760 kb
****************************************************************/

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int M=+;
const int P=+;
typedef long long ll;
inline void Mod_add(int &a,int b){
    if((a+=b)>=P)a-=P;
}
inline int Mod(int x){
    if(x>=P)return x-P;
    if(x<)return x+P;
    return x;
}
int prime[M>>],phi[M],s[M],sf[M],t=;
inline void Eular(){
    phi[]=;
    for(int i=;i<M;++i){
        if(!sf[i])prime[t++]=i,phi[i]=i-,sf[i]=i;
        for(int j=,p;j<t&&l*(p=prime[j])*i<M;++j){
            sf[i*p]=p;
            if(i%p==){phi[i*p]=p*phi[i];break;}
            phi[i*p]=phi[i]*(p-);
        }
    }
    for(int i=;i<M;++i)
        s[i]=Mod(s[i-]+phi[i]);
}
struct hash_table{
    int tot,head[];
    struct Edge{
        int s,c,nxt;
    }edge[];
    inline hash_table(){memset(head,-,sizeof(head));}
    inline void add(int w,int &x,int &c){
        edge[tot]=(Edge){x,c,head[w]};
        head[w]=tot++;
    }
    inline int find(int &x){
        int w=x>>;
        for(int i=head[w];~i;i=edge[i].nxt){
            int s=edge[i].s;
            if(s==x)return edge[i].c;
        }
        return -;
    }
    inline void insert(int &x,int &val){
        add(x>>,x,val);
    }
}mp;
inline int verphi(int x){
    if(x<M)return s[x];
    int w=mp.find(x);
    if(~w)return w;
    int k=;
    for(int i=,s;i<=x;++i){
        s=x/(x/i);
        Mod_add(k,(ll)(s-i+)*verphi(x/i)%P);
        i=s;
    }
    k=(((ll)x*(x+)>>)-k)%P;
    mp.insert(x,k);
    return k;
}
inline int Divide(int x){
    int res=;
    for(int i=;prime[i]*prime[i]<=x;++i)
        if(x%prime[i]==){
            int c=;
            for(;x%prime[i]==;++c)x/=prime[i];
            for(--c;c--;)res*=prime[i];
        }
    return res;
}
inline int sum(int n,int m){
    if(!m)return ;
    if(m==)return phi[n];
    if(n==)return verphi(m);
    int &k=sf[n];
    return ((ll)sum(n/k,m)*(k-)+sum(n,m/k))%P;
}
int f[];
int main(){
    Eular();
    int n,m,ans=;
    scanf("%d %d",&n,&m);
    memset(f,-,sizeof(f));
    for(int i=;i<=n;++i){
        ll k=Divide(i),t=i/k;
        if(~f[t])Mod_add(ans,k*f[t]%P);
        else Mod_add(ans,k*(f[t]=sum(t,m))%P);
    }
    printf("%d\n",ans);
    return ;
}