数论 筛法 mobius反演 min25筛    发布于 2020-03-29   111人围观   0条评论

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]

查看更多
数论 mobius反演 筛法 min25筛    发布于 2020-03-29   105人围观   0条评论
#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;
     
查看更多
思维题 筛法    发布于 2019-09-11   451人围观   0条评论

题目大意

给出100个数,求问是否存在某个连续的100个φ值,使得两者一一相等。

1≤ai≤1.5*108

题解

首先其实能想到的是KMP,但是无奈这个ai太大了,用欧拉筛没办法筛出来,而且时间也不够,因为还有多组数据。

但是能够预处理一些φ还是好的,这样能降低所有数据都需要暴力算φ带来的复杂度。

然后我们猜想,是不是这100个数里面一定会有一个数对应的φ恢复到φ-1的时候是素数,也即两个相邻素数一定相隔100以内?
答案是否定的,这个可以通过打表来检查出来。

但是我们可以找到另一个问题,这100个数的φ-1中,要么就是有至少一个素数,要么就是有一个数为一个≤13的素数和一个大素数的乘积。

这样我们可以直接分开讨论,把所有可能的情况计入一个vector里面,最多出现1000种可能(实际上到不了),然后直接对于每一种可能暴力检索100个数是否符合要求即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;
int phi[maxn];
int pr[maxn],np[maxn];
int cnt = 0;
void euler(){
    phi[1] = 1;
    for(int i = 2;i < maxn;++i){
        if(!np[i]){
            pr[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j <= cnt && i * pr[j] < maxn;++j){
            np[i*pr[j]] = 1;
            if(i % pr[j] == 0){
                phi[i*pr[j]] = phi[i] * pr[j];
                break;
            }
            else phi[i*pr[j]] = phi[i] * (pr[j] - 1);
        }
    }
    return;
}
int mx = 0,mi = 1e9;
int a[105];
int n;
int t;
int calc(int x){//暴力求解φ(x
查看更多