Tag-mobius反演

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-03-29 17:13:37 |  0 Comments  |  数论 筛法 mobius反演 min25筛

HDU6417 Rikka with APSP min25筛+mobius反演

title

题目大意

给出一张n个点的完全图,两点ij (i<j)的路径的距离被定义为:
dis(i,j)=mink[ijk=x2,xZ+]
dij 表示i到j的最短距离,求1i<jndij

题解

题目挺绕的,可能会让人误以为是图论题。但是一看数据范围就不是。所以就来考虑最短路的性质。
显然的,假设节点i,j的编号分别被进行了质因子分解,表达成唯一分解定理的表达式,那么两点的最短距离,如果在两节点编号各质因子的幂次的奇偶性均相同时为1,否则一定为:
dij=pk[i=xpkn,j=ypkm] 其中x,y均没有pk为因子,且n,m奇偶性不同。
很简单,如果两点有多个因子不同,那么我们完全可以途经其它节点来走,让质因子相加取代相乘,这样一定是最小的。
于是就可以直接分最短路径为1和不为1两种情况来讨论。
首先讨论为1的情况,这种情况下我们把两数a,b指数为奇数的pk乘在一起,假设为c,这样ac,bc就是两个介于[1,nc]

 2020-03-29 17:11:22 |  0 Comments  |  数论 mobius反演 筛法 min25筛

HDU6417 Rikka with APSP min25筛+mobius反演 题解代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
typedef long long ll;
ll g[maxn],w[maxn],id1[maxn],id2[maxn],spr[maxn],smu[maxn],pr[maxn];
int nop[maxn],mu[maxn];
const ll mod = 998244353;
int tot = 0,cnt = 0;
void euler_init(){
    nop[1] = 1;
    mu[1] = 1;
    smu[1] = 1;
    for(int i = 2;i < maxn;++i){
        if(!nop[i]){
            mu[i] = -1;
            pr[++tot] = i;
            spr[tot] = spr[tot-1] + i;
        }
        smu[i] = smu[i-1] + (mu[i] == 0 ? 0 : 1);
        for(int j = 1;j <= tot && pr[j] * i < maxn;++j){
            nop[pr[j] * i] = 1;
            if(i % pr[j] == 0){
                mu[i*pr[j]] = 0;
                break;
            }
            mu[i*pr[j]] = -mu[i];
        }
    }
    return;
}
ll A(ll n,ll p){
    if(p*p > n)return n / p;
    return n/p - A(n/p,p);
}
ll S(ll n){
    if(n < maxn)return smu[n];
    ll ans = 0;
    for(ll d = 1;d*d <= n;++d){
        if(mu[d] == 1)
            ans = (ans + n / d / d % mod) % mod;
     
Title - Artist
0:00