Tag-数论

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;
     
 2019-11-06 22:11:12 |  0 Comments  |  数论 数学

BZOJ 2242 SDOI2011 计算器

题解

第一问快速幂

第二问是扩展欧几里得算法求不定方程

第三问使用BSGS算法求离散模对数

三个函数直接看代码吧……纯板子题……

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get_num(){
    ll num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
ll y,z,p;
map<ll,ll>mp;
ll quick_pow(ll a,ll b,ll mod){
    ll ret = 1;
    while(b > 0){
        if(b & 1){
            ret = ret * a;
            ret %= mod;
        }
        b >>= 1;
        a = a * a;
        a %= mod;
    }
    return ret;
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(b == 0){
        d = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b,a%b,d,x,y);
    ll tp = x;
    x = y;
    y = tp - (a / b) * y;
    return;
}
void BSGS(ll y,ll z,ll p){
    mp.clear();
    y %= p;
    if(y == 0 && z == 0){
        cout << "1" 
 2019-10-05 21:34:07 |  0 Comments  |  DP bitset 数论

牛客国庆欢乐赛5 2017四川省赛 K-2017Revenge bitset加速dp、原根

题目大意

给出n个数,要你从中选出一些数,使得他们的乘积mod 2017的余数为r,问总方案数mod 2的值。

题解

对于一些数的乘法,我们可以用log把他转化乘加法。

但是是在模意义下,就是需要离散模对数了。

这时候我们要求2017的原根,2017的原根是5,我们就可以自然而然的把原来的所有数都化为他们的离散模对数了。

首先如果数据范围很小,我们该怎么写呢?

那么我们可以用dp[i][j]表示当前为第枚举到第i个数,选出的前面的(包括i)所有数的乘积的离散模对数为j的方案数。

那么dp方程就很容易能够想到了:

dp[i][j] = dp[i-1][j] + (dp[i-1][(j-lg[a[i]])%2016]);

这两项分别代表当前项选/不选的情况。

可以看到第i位的值只跟他的前一位有关,所以空间可以滚动掉一维。

但是这样的时间仍然是O(n*2016),n的数据范围让我们无法直接这样去做dp(而且由于依赖性无法使用多线程,这里我又在说胡话了)。

那我们该怎么办?

我们注意一下,答案只需要输出总方案数mod 2的值,所以注意一下dp方程,我们就可以这样去改了:

dp[i][j] = dp[i-1][j] ^ (dp[i-1][(j-lg[a[i]])%2016]);(二进制中的异或运算实际上就是加法对2取模)

也就是dp[j] = dp[j] ^ dp[(j-lg[a[i]])%2016];

计算机系统在进行二进制运算的时候是非常快的,所以可以用二进制的一些东西来加速这个运算,让枚举2016次的复杂度降低成为一个更小的常数,但是通常的数据类型不支持我们这么做。

这时候我们可以用C++中的bitset来对上面的式子进行加速。

如果我们用一个2016位的bitset<2016>f,那么上面的递推式就要写成以下形式:

f ^= (f<<lg[a[i]]) ^ (f>>(2016-lg[a[i]]));

这样由于计算机系统在对于bitset运算的速度较快,我们就可以通过此题了。

注意一定要用cout输出,printf输出会有问题。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
int lg[2020],a[2000005],n,r;
bitset<2016>f;
int main(
 2019-08-26 00:04:09 |  0 Comments  |  数论

2019 CCPC网络赛 1005 huntian oy 杜教筛

图片标题

题目大意

给定n,a,b,其中a,b保证互质m,求
f(n,a,b)=i=1nj=1igcd(iaja,ibjb)[gcd(i,j)==1] 对1e9+7取模的结果。

题解

这就当作博主杜教筛的入门题吧……
首先我们手完一下数据,不难发现gcd(iaja,ibjb)=igcd(a,b)jgcd(a,b)(别问证明,证明很长……这个手玩也是我队友玩出来的)
于是f(n,a,b)这个看起来极度复杂的式子,我们就可以如同以下化简。
f(n,a,b)=i=1nj=1i(igcd(a,b)jgcd(a,b))[gcd(i,j)==1]

 2019-06-04 00:08:00 |  0 Comments  |  数论 同余线性方程

POJ 青蛙的约会 扩展欧几里得解同余线性方程

题解

青蛙的世界真是简单啊,而人类就不一样了QAQ

扯远了扯远了……

对这个题目进行比较小的数学建模,我们可以得到这样一个式子

然后我们移一下项,可以得到 

我们要求解的就是t的最小值。

上式可以转化以下一元二次不定方程: 

然后我们都清楚一元二次不定方程的解法无非就是扩展欧几里得……

其中如果gcd((m-n),l)不能整除(y-x)的话,此方程则是无解的,直接输出Impossible。

否则的话,就利用扩展欧几里得去计算t。

先对两边式子的系数同时除以gcd((m-n),l),利用扩展欧几里得算法解出a*t’ + b*p‘ = 1的解中的t’,然后再乘(y-x)/gcd(m-n,l)转化为需要的t。

此时不一定能够保证t为最小非负值。只需要t 对 (l/gcd((m-n,l)))取膜(如果t<0则取膜后再加膜数),即得到最终结果。

扩展欧几里得算法的讲解与证明将在之后的一篇博客中给出。

代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
ll a, b, n, m, l;
void gcd(ll a, ll b, ll &d, ll &x, ll &y){
    if(b == 0){
    	x = 1;
    	y = 0;
    	d = a;
    	return;
    }
    gcd(b, a % b, d, x, y);
    ll tp = x;
    x = y;
    y = tp - (a / b) * y;
    return;
}
ll ans,ans2,g;
int main(){
    while ((cin >> a >> b >> m >> n >> l)){
        ll sp = m - n;
        ll d = b - a;
        if(sp < 0){
            sp = -sp;
            d = -d;
        }
    	if(sp == 0 && d != 0){
    		cout 
Title - Artist
0:00