HDU-4947 GCD Array(反演)

GCD Array

$Description$
Teacher Mai finds that many problems about arithmetic function can be reduced to the following problem:
Maintain an array a with index from $1$ to $l$ . There are two kinds of operations:

Add $v$ to $a_x$ for every $x$ that $gcd(x,n)=d$ .
Query $\sum_{i=1}^{x}a_i$

$Solution$

插入操作：

$a_x=v\cdot [gcd(x,n)=d]= \sum_{k|\frac{x}{d},k|\frac{n}{d}}v\cdot \mu(k)=\sum_{k\cdot d|x,k\cdot d|n}v\cdot \mu(k)$
$令f(k\cdot d)=v\cdot \mu(k)[k\cdot d|n],a_x=\sum_{k\cdot d|x}f(k\cdot d)=\sum_{t|x}f(t)$
$所以用树状数组维护f数组的值即可$
2. 查询操作：

$\sum_{i=1}^{x}a_i=\sum_{i=1}^{x}\sum_{d|i}f(d)=\sum_{d=1}^{x}f(d)\sum_{i=1}^{x}[d|i]=\sum_{d=1}^{x}f(d)\cdot \left \lfloor \frac{x}{d}\right \rfloor$

$Code$

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
#define sc scanf
#define itn int
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
using namespace std;
const int N=2e5+125;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=x*(a/b);}
int n,Q;
ll f[N];
void up(int x,int val){for(int i=x;i<=n;i+=i&-i)f[i]+=val;}
ll sum(int x){
    ll ans=0;
    for(int i=x;i;i&=i-1)ans+=f[i];
    return ans;
}
short int mu[N];
vector<int>fac[N];
void pre(){
    mu[1]=1;
    for(int i=1;i<N;i++){
        fac[i].push_back(i);
        for(int j=i+i;j<N;j+=i){
            mu[j]-=mu[i];
            fac[j].push_back(i);
        }
    }
}
int main(){
    pre();
    while(scanf("%d%d",&n,&Q)&&(n+Q)){
        for(int i=0;i<=n;i++)f[i]=0;
        static int sa=1;
        printf("Case #%d:\n",sa++);
        for(int cas=1;cas<=Q;cas++){
            int op;sc("%d",&op);
            if(op==1){
                int m,d,v;
                sc("%d%d%d",&m,&d,&v);
                if(m%d)continue;
                int sz=fac[m/d].size();
                for(int i=0;i<sz;i++)up(fac[m/d][i]*d,mu[fac[m/d][i]]*v);
            }else{
                int m;sc("%d",&m);
                ll ans=0;
                for(int i=1,last;i<=m;i=last+1){
                    last=m/(m/i);
                    ans+=m/i*(sum(last)-sum(i-1));
                }
                printf("%lld\n",ans);
            }
        }
    }
}