[题解] 最小生成树(msta)

题目描述

话说正在 $jmy$ 愁苦如何筹钱给大家买汽水的时候，他遇上了一位魔法师。魔法师希望 $jmy$ 能帮他破解魔法书的咒语。如果 $jmy$ 做到了，就帮他付所有买汽水的钱。

魔法书上画了一个完全图（每对不同的顶点之间有且只有一条边），每个点都有一个独一无二的 $[1,n]$ 内的编号，$jmy$ 的任务是要找到最小生成树，以此作为魔法树，从而破解咒语。

对于完全图的边 $(i，j)$ $(i≠j)$ 的边权恰好就等于 $i，j$ 两个数字的最大公约数。特别地，要作为魔法树，必须满足树指定某个点为根后，所有除根以外的节点的父亲的标号必须小于自身标号。

$jmy$ 一眼就看出了最小生成树的边权和。然而咒语却是最小生成树的个数。为了保证大家都有汽水喝，你能帮帮 $jmy$ 吗？

输入格式

一行一个整数 $N$，表示完全图的大小

输出格式

一行一个整数，表示对 $100000007$ 取模的结果

样例输入

3

样例输出

2

数据范围

对于 $10 \%$ 的数据，$N \leq 5$
对于 $30 \%$ 的数据，$N \leq 8$
对于 $40 \%$ 的数据，$N \leq 10$
对于 $70 \%$ 的数据，$N \leq 5000$
对于 $100 \%$ 的数据，$N \leq 20000$

解题思路

首先我们考虑最小生成树的权值和为多少。

$1$ 与其他任何数的最大公约数都为 $1$

不难发现最小生成树的权值和为 $n-1$，每条边边权必须为 $1$

对于每一个节点，我们考虑哪些节点 $a$ 可以是这个节点 $b$ 的父亲

也就是求解 $a < b$ 且 $gcd(a, b) = 1$ 的个数，相乘即可

就是线性筛欧拉函数QAQ

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 100000 + 10;
const int MOD = 1e8 + 7;

int n;
int prime[MAXN], cnt;
long long phi[MAXN];
bool isPrime[MAXN];

int main(){
    scanf("%d", &n);

    phi[1] = 1;

    for(register int i=2; i<=n; i++){
        if(!isPrime[i]){
            prime[++cnt] = i;
            phi[i] = i - 1;
        }

        for(register int j=1; j<=cnt; j++){
            if(i * prime[j] > n)
                break;

            isPrime[i * prime[j]] = true;

            if(i % prime[j] == 0){
                phi[i * prime[j]] = phi[i] * prime[j];
                phi[i * prime[j]] %= MOD;
                break;
            }else
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
                phi[i * prime[j]] %= MOD;
        }
    }   

    long long ans = 1;
    for(register int i=1; i<=n; i++){
        ans *= phi[i];
        ans %= MOD;
    }

    printf("%lld", ans);
    return 0;
}