【HDU 4676 Sum Of Gcd】莫隊算法

HDU4676

題意就是求某個區間内兩兩gcd之和。

關于一個區間内兩兩GCD之和，我們有一個推導：

對一個序列的某個區間L,R，每個數兩兩之間的GCD之和為

Σd|nφ(d)×C2num(d) Σ d | n φ ( d ) × C n u m ( d ) 2

d在這裡指這個區間的所有約數

通過這個公式，我們就可以很友善的通過枚舉新加進來的數字的因子進行add和del,推算一下就可以了。

這裡每個數的因子和歐拉函數要與處理一下保證複雜度。

代碼

#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define dbg(x) cout<<#x<<" = "<<x<<endl
const int maxn = +;
struct data
{
    int l,r,id;
}Q[maxn];
int pos[maxn];
int phi[maxn];
int pri[maxn];
int a[maxn];
int ans[maxn];
int Flag[maxn];
vector<int> v[maxn];
int num[maxn];
bool cmp(const data &a,const data &b)
{
    if(pos[a.l]==pos[b.l]) return a.r<b.r;
    return pos[a.l]<pos[b.l];
}
void Getphi(int Max)//歐拉函數與因子的預處理
{
    phi[] = ;
    for (int i = ; i <= Max; i ++)
    {
        if (!Flag[i])
        {
            phi[i] = i - ;
            pri[++ pri[]] = i;
        }
        for (int j = ; j <= pri[]; j ++)
        {
            if (l * i * pri[j] > Max) break;
            Flag[i * pri[j]] = ;
            if (i % pri[j] == )
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            phi[i * pri[j]] = phi[i] * (pri[j] - );
        }
    }
    for(int i=;i<=Max;i++)
    {
        for(int j=i;j<=Max;j+=i)
            v[j].push_back(i);
    }
}
int L=,R=;
long long Ans=;
void add(int x)
{
    for(int i=;i<v[a[x]].size();i++)
        Ans+=L*phi[v[a[x]][i]]*num[v[a[x]][i]];
    for(int i=;i<v[a[x]].size();i++)
        num[v[a[x]][i]]++;
    return ;
}
void del(int x)
{
    for(int i=;i<v[a[x]].size();i++)
        num[v[a[x]][i]]--;
    for(int i=;i<v[a[x]].size();i++)
        Ans-=L*phi[v[a[x]][i]]*num[v[a[x]][i]];
    return ;
}
int main()
{
    int n,q;
    int t;
    int cnt=;
    Getphi();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        L=,R=,Ans=;
        for(int i=;i<=n;i++) num[i]=;
        int sz=sqrt(n);
        for(int i=;i<=n;i++)
        {
            scanf("%d",&a[i]);
            pos[i]=i/sz;
        }
        scanf("%d",&q);
        for(int i=;i<=q;i++)
        {
            scanf("%d%d",&Q[i].l,&Q[i].r);
            Q[i].id=i;
        }
        sort(Q+,Q++q,cmp);
        for(int i=;i<=q;i++)
        {
            while(R<Q[i].r)
            {
                R++;
                add(R);
            }
            while(L>Q[i].l)
            {
                L--;
                add(L);
            }
            while(L<Q[i].l)
            {
                del(L);
                L++;
            }
            while(R>Q[i].r)
            {
                del(R);
                R--;
            }
            ans[Q[i].id]=Ans;
        }
        printf("Case #%d:\n",cnt++);
        for(int i=;i<=q;i++)
        printf("%d\n",ans[i]);
    }
    return ;
}
           

友情推薦莫隊算法專題連結