A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2705: [SDOI2012]Longge的问题
发表于: | 分类: Oi | 评论:0 | 阅读:136

以后的题尽量都写写题解吧,便于以后总结

$ans = \sum{\gcd(i,N)}$

然后我们枚举一个$t$满足$t|N$,其实就是莫比乌斯反演

然后问题就变成了$ans = \sum\limits_{t|N}t*\sum\limits_{i=1}^N{[\gcd(i,N) == t]}$

再变一下

$ans = \sum \limits_{t|N}t*\sum \limits_{i=1}^N{[\gcd(\frac{i}{t},\frac{N}{t})==1]}$

然后……然后就好办了吧,注意到$i$始终都是$<N$的,所以后面的那个求和实际上就是一个$\phi(n)$

然后就直接$O(\sqrt{n})$求解就行了

我分解质因数打错了,最后排才拍出来……最近真是老了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+5;
LL a[N], b[N];
 
inline void calc(LL x) {
    register int  i = 1;
    int cnt = 0;
    for(;(LL)i*i<x;++i) {
        if(x%i==0) {
            a[++cnt] = i;
            a[++cnt] = x / i;
        }
    }
    if(i*i==x) a[++cnt] = i;
}
 
inline LL phi(LL x) {
    register int i = 2;
    LL ans = x;
    int cnt = 0;
    for(;(LL)i*i<=x;++i) {
        if(x%i==0) {
            b[++cnt] = i;
            while(x%i==0) 
                x /= i;
        }
    }
    if(x != 1) b[++cnt] = x;
    for(i=1;i<=cnt;++i) ans = ans / b[i] * (b[i]-1);
    return ans;
}
 
int main() {
    LL n;
    cin >> n;
    calc(n);
    LL ans = 0;
    for(int i=1;a[i];++i) 
        ans += (LL)a[i] * phi(n/a[i]);
    cout << ans << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP