ACM-ICPC 2018 南京赛区网络预赛 Sum

ACM-ICPC 2018 南京赛区网络预赛 Sum

题意不复述
对数x进行质因数分解，

f(x)的求法

$x={\prod }_{i=1}^k{\prod }_{j=1}^{c_i}{p}_{i,j}^i$x=∏i=1k​∏j=1ci​​pi,ji​
$k\le 3\Rightarrow f\left(x\right)=0$k≤3⇒f(x)=0
$k\le 2\Rightarrow f\left(x\right)=2^{c_1}$k≤2⇒f(x)=2c1​

说人话就是如果分解质因数后：
如果有一个质因子 $p$p的指数大于等于3，鸽笼原理知 $a,b$a,b必然有一个含有两个 $p$p,那么 $x$x肯定无法分解成两个square-free integer $a,b$a,b.
如果有一个质因子 $p$p的指数等于2,鸽笼原理知 $a,b$a,b必然有一个含有两个 $p$p,那么没得选， $a,b$a,b各分一个 $p$p.
如果有一个质因子 $p$p的指数等于1,那么 $p$p不是给 $a$a就是给 $b$b.

指数为1的质因子个数是 $c_1$c1​,故总方案数
$f\left(x\right)=2^{c_1}$f(x)=2c1​

f(x)性质

知道了 $f\left(x\right)$f(x)表达式之后，就可以推导出 $f\left(x\right)$f(x)的性质了。
约定 $p$p表示质数

1. $p\nmid x\Rightarrow f\left(px\right)=2f\left(x\right)$p∤x⇒f(px)=2f(x)
2. $p\mid x,p^2\nmid x\Rightarrow f\left(px\right)=f\left(\frac{x}{p}\right)$p∣x,p2∤x⇒f(px)=f(px​)
3. $p^2\mid x\Rightarrow f\left(px\right)=0$p2∣x⇒f(px)=0
4. $f\left(p\right)=2,f\left(1\right)=1$f(p)=2,f(1)=1

所以使用欧拉筛法的遍历顺序，使得每个f只会被求一次即可。
预处理所有 $f$f和 $f$f的前缀和

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e7+10;
const int max_prime_cnt = 1271356;
bool is_prime[maxn];
int prime[max_prime_cnt];
int prime_cnt;
int f[maxn];
ll sf[maxn];
int n;
void get_f(int n) {
    memset(is_prime,1,sizeof(is_prime));
    is_prime[1] = false;
    f[1] = 1;
    prime_cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime[prime_cnt++] = i;
            f[i] = 2;
        }
        int k = n/i;
        for (int j = 0; j < prime_cnt && prime[j] <= k; ++j) {
            is_prime[i*prime[j]] = false;
            if (i%prime[j] == 0) {
                int t = i/prime[j]; // t*prime[j]^2
                f[i*prime[j]] = t%prime[j] ? f[t] : 0;
                break;
            } else {
                f[i*prime[j]] = 2*f[i];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    n = maxn-5;
    get_f(n);
    sf[0] = 0;
    for (int i = 1; i <= n; ++i)
        sf[i] = sf[i-1]+f[i];
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        cout<<sf[n]<<endl;
    }
    return 0;
}