P3455 [POI2007]ZAP-Queries

· · 题解

这是一道比较简单的莫反题，还记得某巨巨说过，可以用莫比乌斯反

演解决的问题绝大部分都可以用\mu函数的性质解决。

然而我太菜了

\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j) \sum_{d=1}^nd*\sum_{i=1}^{[n/d]}\sum_{j=1}^{[m/d]}[gcd(i,j)==1]

即：

\sum_{d=1}^nd*\sum_{i=1}^{[n/d]}\sum_{j=1}^{[m/d]}\sum_{k|gcd(i,j)}\mu(k)

也就是：

\sum_{d=1}^nd*\sum_{k=1}^{[n/d]}\mu(k)\sum_{i=1}^{[n/(kd)]}\sum_{j=1}^{[n/kd]}1

然后：

\sum_{d=1}^nd*\sum_{k=1}^{[n/d]}\mu(k)*(1+[n/kd])^2*([n/kd])^2

于是我们发现后面的的那堆平方可以O(1)算出来，然后两次数论分

块就可以求出来了

蒟蒻的代码

#include<iostream>
#include<cstdio>
using namespace std;
#define Mod 20101009
#define Min(x,y) x>y?y:x
#define N 10000055
#define int long long
int mu[N] , g[N] , vis[N] , p[N] ;
int num ;
void Init(int x)
{
    mu[1] = 1 ;
    g[1] = 1 ;
    for(int i = 2 ; i <= x ; i++ ){
        if( !vis[i] ) p[++num] = i , mu[i] = -1 ;
        for(int j = 1 ; j <= num && p[j] * i <= x ; j++ ){
            vis[ p[j] * i ] = 1 ;
            if( i % p[j] == 0 ) break ;
            mu[ p[j] * i ] = -mu[i] ;
        }
        g[i] = ( g[ i - 1 ] + 1ll*i * i % Mod * ( mu[i] + Mod ) ) % Mod ;
    }
    return ;
}
int Sum(int x )
{
    return ( ( x + 1 ) * x / 2 ) % Mod ;
}
int Ask(int x ,int y)
{
    int ans = 0 ;
    if( x > y ) swap( x , y ) ;
    for(int l = 1 , r ; l <= x ; l = r + 1 ){
        r = Min( x / ( x / l ) , y / ( y / l ) ) ;
        ans = ( ans + 1ll*( g[r] - g[l - 1] + Mod ) % Mod * ( Sum( x / l ) * Sum( y / l ) ) % Mod ) % Mod ;
    }
    return ans % Mod ;
}
signed main()
{
    int n , m ;
    scanf("%lld%lld" , &n , &m ) ;
    if( n > m ) swap( n , m ) ;
    Init(m+10) ;
    long long ans = 0 ;
    for(int l = 1 , r ; l <= n ; l = r + 1 ){
        r = Min( n / ( n / l ) , m / ( m / l ) ) ;
        ans = ( ans + 1ll * ( 1ll * ( r - l + 1 ) * ( l + r ) / 2  ) % Mod * Ask( n / l , m / l ) % Mod ) % Mod ;
    }
    printf("%lld\n" , ans % Mod ) ;
}