codeforces#305 547 C.C.Mike and Foam(モビウス反転)

タイトルリンク:
クリックしてリンクを開く
テーマ:
1列の数を与えて、最初の集合は空で、それからq回の操作、毎回1つのxを与えて、もしx番目の数が存在するならば、削除して、追加が存在しないで、操作が終わった互質の数がどれだけ対があるかを聞きます
テーマ分析:
互質の数の対数を聞いて、裸の数の論題
まずf(k)はgcd(ai,aj)と定義する(1<=i
定義F(k)はk|gcd(ai,aj)(1<=i
では,モビウスの反転定理の第2の形式からf(k)=sigma(d>=1)[u(d)*F(d*k)]を得た.
cnt[i]をコレクション内のiの倍数の数として定義する数
F(k)＝C(2,cnt［k］)の結論は明らかである.
モビウスの反転を利用して、追加または削除する数に基づいて結果を修正し、出力すればいいのです
すなわち、与えられた数に対して素因数を分解し、現在の数がある素因数の2次方以上を含む場合、uは0に等しい
しかも2*3なので.....*17>500000なので、素因数の個数は6個を超えず、2^6種の影響を及ぼすF(k)を列挙すればよい
総複雑度q*2^6、絶対的な秒出

#include 
#include 
#include 
#include 
#include 
#define MAX 500007

using namespace std;

typedef long long LL;

int n,q,x;
int a[MAX];
int u[MAX];
int used[MAX];
int cnt[MAX];
int maxPrime[MAX];
vector v;

LL ans;

void init ( )
{
    memset ( maxPrime , -1 , sizeof ( maxPrime ) );
    for ( int i = 1 ; i < MAX ; i++ ) u[i] = 1;
    for ( int i = 2 ; i < MAX ; i++ )
    {
        if ( ~maxPrime[i] ) continue;
        for ( int j = 1 , t = i ; t < MAX ; j++,t += i )
        {
            maxPrime[t] = i;
            u[t] = j%i==0?0:-u[t];
        }
    }   
}

void update ( int x , int f )
{
    v.clear();
    while ( x > 1 )
    {
        int p = maxPrime[x];
        v.push_back(p);
        while ( x%p == 0 )
            x /= p;
    }
    int m = v.size();
    int total = 1<