Loading [MathJax]/jax/output/CommonHTML/jax.js

嘘~ 正在从服务器偷取页面 . . .

U_


UVA11424 GCD - Extreme (I) 题解

题目链接:UVA11424 GCD - Extreme (I)

题意

给定 n ,求

ni=1nj=i+1gcd(i,j)

1<n2×105 ,最多 2×104 组数据。

据说是「7倍经验」,那我干脆一并写了吧。

这道题有很多种解法,常见的解法是欧拉函数和莫比乌斯反演。

解法1:欧拉函数

正解解法。记 f(n)=ni=1gcd(i,n) ,则答案为 ni=1f(i)

考虑怎么快速计算 f 。设 g(i,n) 为对于所有的 x(1x<n)gcd(x,n)=ix 的个数,则

f(n)=dng(d,n)

注意到 gcd(x,n)=i ,意味着 gcd(x/i,n/i)=1 ,也就是 x/in/i 互质,故

f(n)=dnφ(n/i)

感觉有点对劲,但好像又不是很对劲。直接枚举因数会比较慢,因此我们可以反过来计算贡献。

时间复杂度 O(nlogn)

代码:

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))


bitset<N> ck; int pcnt,phi[N],f[N],sum[N],prime[N];
void Euler(int n = N - 10)
{
    phi[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!ck[i]) { prime[++pcnt] = i; phi[i] = i - 1; }
        for(int j = 1; j <= pcnt && i * prime[j] <= n; j++)
        {
            int pos = i * prime[j]; ck[pos] = true;
            if(i % prime[j]) { 
                phi[pos] = phi[i] * phi[prime[j]];
            } else { phi[pos] = phi[i] * prime[j]; break; }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    Euler();
    for(int i = 1; i <= N - 10; i++)
        for(int j = i * 2; j <= N - 10; j += i) f[j] += i * phi[j / i];
    sum[2] = f[2];
    for(int i = 3; i <= N - 10; i++) sum[i] = sum[i - 1] + f[i];
    for(int n; cin >> n && n != 0; ) cout << sum[n] << '\n';
    return 0;
}

解法2:莫比乌斯反演

这个也是我自己想到的解法(不是正解),不过在这道题就需要卡一卡常。

我们先来推推式子:(这个式子的结果 x 与原答案 x0 的关系为 x=2x0+n(n+1)2

ni=1nj=1gcd(i,j)=nk=1kni=1nj=1[gcd(i,j)=k]=nk=1kn/ki=1n/kj=1[gcd(i,j)=1]=nk=1kn/ki=1n/kj=1dgcd(i,j)μ(d)=nk=1kn/kd=1μ(d)n/ki=1[di]n/kj=1[dj]=nk=1kn/kd=1μ(d)nkd2

然而直接搞是过不了的,因为数据组数太多:

O(n1+n2++nn)=O(n(1+12++1n))=O(n)

考虑设 m=n/k ,则

nk=1kmd=1μ(d)md2

后面的部分在 m 固定时与 k 无关,考虑预处理为 f(m) ,则

nk=1kf(n/k)

时间复杂度 O(NN) ,但是需要卡常,原理参考link

代码:(用时 1.17s )

cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename A, typename ...B>
        void read(A &x, B &...y) { return read(x), read(y...); }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(2e5 + 15))


bitset<N> ck; int pcnt,mu[N],f[N],v[N],prime[N];
void Mobius(int n = N - 10)
{
    mu[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!ck[i]) { prime[++pcnt] = i; mu[i] = -1; }
        for(int j = 1; j <= pcnt && i * prime[j] <= n; j++)
        {
            int pos = i * prime[j]; ck[pos] = true;
            if(i % prime[j]) { mu[pos] = -mu[i]; } else { mu[pos] = 0; break; }
        }
    }
    for(int i = 1; i <= n; i++) mu[i] += mu[i - 1];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    Mobius();
    for(int i = 1; i <= N - 10; i++)
    {
        int sq = sqrt(i), cnt = 2 * sq;
        for(int j = 1; j <= sq; j++) { v[j] = j; v[cnt - j + 1] = i / j; }
        for(int k = 1, j = cnt; k <= cnt; k++,j--) f[i] += v[k] * v[k] * (mu[v[j]] - mu[v[j - 1]]);
    }
    for(int n; read(n), n != 0; )
    {
        int res = 0;
        for(int l = 1, r; l <= n; l = r + 1)
        {
            r = n / (n / l);
            res += (f[n / l] - 1) * (l + r) * (r - l + 1) / 2;
        }
        write(res / 2); pc('\n');
    }
    return 0;
}

其他题

  1. UVA11426 拿行李(极限版) GCD - Extreme (II) 只需要把 N 改一下就能过了。
  2. 洛谷P1390 公约数的和 删掉多组询问,然后把 N 改一下就能过了。
  3. 洛谷P2398 GCD SUM 删掉多组询问,把 N 改一下,把输出改一下就能过了。
  4. 洛谷P2568 GCD 写过题解,看这边 link
  5. SP3871 GCDEX - GCD Extreme 只需要把 N 改一下就能过了(搬题小能手SPOJ)
  6. UVA11417 GCD 本题简化版,直接交
  7. 算上本题,正好7倍经验,蛮好的。

文章作者: q779
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
评论
你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3