bzoj3561

3561: DZY Loves Math VI

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 240  Solved: 163
[Submit][Status][Discuss]

Description

给定正整数n,m。求

 

 

Input

一行两个整数n,m。

Output

一个整数，为答案模1000000007后的值。

Sample Input

5 4

Sample Output

424

HINT

数据规模：

1<=n,m<=500000，共有3组数据。

Source

By Jcvb

挖坑

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

upd 9.15 我来填坑了 又做了一遍...

套路推导一番我们可以得到一个式子，我不会写LaTeX。。。。。。请移步lych大神的博客

然后重点在于怎么求值，其实暴力就行了，我们观察那个式子，其实我们只需要求到min(n/i,m/i)就行了，然后发现这样其实是调和级数，那么我们每次先把1->min(n/i,m/i)的sum调和级数更新一下，然后再调和级数计算答案，我们看后面那个i^d*j^d其实刚才被更新过了，直接O(1)就可以算出来，然后枚举p也是调和级数的，所以总的复杂度还是O(NlogN)  完了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010, mod = 1000000007;
int n, m;
ll ans;
ll mu[N], a[N], sum[N];
int p[N], mark[N];
ll power(ll x, ll t)
{
    ll ret = 1;
    for(; t; t >>= 1, x = x * x % mod) if(t & 1) ret = ret * x % mod;
    return ret;
}
void Init()
{
    mu[1] = 1;
    for(int i = 2; i <= 1000000; ++i) 
    {
        if(!mark[i])
        {
            p[++p[0]] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= p[0] && p[j] * i <= 1000000; ++j) 
        {
            mark[i * p[j]] = 1;
            if(i % p[j] == 0)
            {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
}
int main()
{
    Init();
    scanf("%d%d", &n, &m);
    if(n > m) swap(n, m);
    for(int i = 1; i <= m; ++i) a[i] = 1;
    for(int d = 1; d <= n; ++d)
    {
        ll delta = 0;
        for(int p = 1; p * d <= m; ++p) 
        {
            a[p] = a[p] * (ll)p % mod;
            sum[p] = (sum[p - 1] + a[p]) % mod;
        }
        for(int p = 1; p * d <= n; ++p) if(mu[p])
            delta = (delta + mu[p] * a[p] % mod * a[p] % mod * sum[n / d / p] % mod * sum[m / d / p] % mod) % mod;        
        ans = (ans + delta * power(d, d) % mod) % mod;
    }
    printf("%lld
", ans);
    return 0;
}

[Submit][Status][Discuss]