代码编织梦想

https://www.acwing.com/activity/content/punch_the_clock/11/

欧拉函数

欧拉公式

在这里插入图片描述

对于每一个数 N N N,都可以分解为 N = p 1 α 1 × p 2 α 2 × ⋯ × p k α k N=p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k} N=p1α1×p2α2××pkαk

其中, p 1 p 2 ⋯ p k p_1 p_2 \cdots p_k p1p2pk为质数, α 1 α 2 ⋯ α k \alpha_1 \alpha_2 \cdots \alpha_k α1α2αk为对应的质数的出现次数

那么,最后的结果为 r e s = N × p 1 − 1 p 1 × p 2 − 1 p 2 × ⋯ × p k − 1 p k res = N \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \cdots \times \frac{p_k - 1}{p_k} res=N×p1p11×p2p21××pkpk1

需要注意的一点

当我们在计算 N × p 1 − 1 p 1 N \times \frac{p_1 - 1}{p_1} N×p1p11的时候,如果我们用 N × ( p 1 − 1 ) N\times (p_1 - 1) N×(p11),那么很容易发生溢出,所以我们采取先计算除法,在计算乘法

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    while (n --) {
        int x;
        cin >> x;
        int res = x;
        for(int i = 2; i <= x / i; i++)
            if(x % i == 0) {
                res = res /i * (i - 1) ;
                while(x % i == 0) x /= i;
            }
        if(x > 1) res = res / x * (x - 1);
        cout << res << endl;
    }
    return 0;
}

筛法求欧拉函数

在这里插入图片描述

思路:

  1. 实现线性筛选法来筛选每一个质数
  2. 对于一个质数 P n P_n Pn来说,他的一个欧拉函数为 P n − 1 P_n - 1 Pn1
  3. 对于一个和数 P n P_n Pn来说,在我们线性筛选质数的过程中,他需要分两种情况:

①. i%primes[j] == 0,说明 p r i m e s [ j ] primes[j] primes[j] i i i的最小质因子,也是 i × p r i m e s [ j ] i \times primes[j] i×primes[j]的最小质因子。所以说,只需要将一开始的基数修改为 p r i m e s [ j ] primes[j] primes[j]即可

r e s ( i ) = i × p 1 − 1 p 1 × p 2 − 1 p 2 × ⋯ × p k − 1 p k ( i = p k ) res(i) = i \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \cdots \times \frac{p_k - 1}{p_k}(i=p_k) res(i)=i×p1p11×p2p21××pkpk1(i=pk) i是一个质数

⇒ r e s ( p r i m e s [ j ] × i ) = p r i m e s [ j ] × i × r e s ( i ) i \Rightarrow res(primes[j] \times i) = primes[j] \times i \times \frac{res(i)}{i} res(primes[j]×i)=primes[j]×i×ires(i)

⇒ r e s ( p r i m e s [ j ] × i ) = p r i m e s [ j ] × r e s ( i ) \Rightarrow res(primes[j] \times i) = primes[j] \times res(i) res(primes[j]×i)=primes[j]×res(i)

② .i % primes[j] != 0,说明 p r i m e s [ j ] primes[j] primes[j]不是 i i i的因子,只是 i × p r i m e s [ j ] i \times primes[j] i×primes[j]的最小质因子。因此,修改基数 1 1 1 p r i m e s [ j ] primes[j] primes[j]后,还需要补上 p r i m e s [ j ] primes[j] primes[j]这个质数的欧拉函数项

r e s ( i ) = i × p 1 − 1 p 1 × p 2 − 1 p 2 × ⋯ × p k − 1 p k res(i) = i \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \cdots \times \frac{p_k - 1}{p_k} res(i)=i×p1p11×p2p21××pkpk1

⇒ r e s ( p r i m e s [ j ] × i ) = p r i m e s [ j ] × i × r e s ( i ) i × p r i m e s [ j ] − 1 p r i m e s [ j ] \Rightarrow res(primes[j] \times i) = primes[j] \times i \times \frac{res(i)}{i} \times \frac{primes[j] - 1}{primes[j]} res(primes[j]×i)=primes[j]×i×ires(i)×primes[j]primes[j]1

⇒ r e s ( p r i m e s [ j ] × i ) = r e s ( i ) × ( p r i m e s [ j ] − 1 ) \Rightarrow res(primes[j] \times i) = res(i)\times (primes[j] - 1) res(primes[j]×i)=res(i)×(primes[j]1)

#include <iostream>
using namespace std;

typedef long long LL;
const int N =  1e6 + 10;
int primes[N],phi[N],cnt;
int vis[N];
int n;

void get_phi() {
    phi[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!vis[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        
        for(int j = 0; primes[j] <= n / i; j ++) {
            vis[primes[j] * i] = 1;
            if(i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
}

int main() {
    cin >> n;
    get_phi();
    
    LL res;
    for(int i = 1; i <= n; i++) res += phi[i];
    cout << res << endl;
    return 0;
}

快速幂

快速幂

在这里插入图片描述

思路

  1. 当指数 k k k 0 0 0的时候,返回 1 1 1
  2. 当指数 k k k为奇数的时候,返回 x × x k − 1 × x k − 1 x \times x^{k-1} \times x^{k-1} x×xk1×xk1
  3. 当指数 k k k为偶数的时候,返回 x k / 2 × x k / 2 x^{k/2} \times x^{k/2} xk/2×xk/2
  • 递归
#include <iostream>

using namespace std;
typedef long long LL;
int n,a,b,c;

LL check(int k) {
    if(k == 0) return 1;
    if(k & 1) return check(k - 1) % c * a % c;
    LL x = check(k / 2);
    return (x * x) % c;
}

int main() {
    cin >> n;
    
    while(n --) {
        cin >> a >> b >> c;
        cout << check(b) << endl;
    }
    return 0;
}
  • 递推
#include <iostream>

using namespace std;
typedef long long LL;
int n,a,b,c;

LL check() {
    LL res = 1;
    while(b) {
        if(b & 1) res = res * a % c;
        a = (LL) a * a % c;
        b >>= 1;
    }
    return res;
}

快速幂求逆元

在这里插入图片描述

n n n为质数的情况

a / b ≡ a × x ( m o d n ) a/b \equiv a \times x \pmod{n} a/ba×x(modn)

同时 × b \times b ×b可以推导出 ⇒ a ≡ a × b × x ( m o d n ) \Rightarrow a \equiv a \times b \times x\pmod{n} aa×b×x(modn)
⇒ 1 ≡ b × x ( m o d n ) \Rightarrow 1 \equiv b \times x \pmod{n} 1b×x(modn)
⇒ b × x ≡ 1 ( m o d n ) \Rightarrow b \times x \equiv 1\pmod{n} b×x1(modn)

费马小定理: 如果p是一个质数,而整数a不是p的倍数,则有 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1\pmod{p} ap11(modp)

由费马小定理可知,当 n n n为质数时, b n − 1 ≡ 1 ( m o d n ) b ^{n-1} \equiv 1 \pmod{n} bn11(modn)
⇒ b × b n − 2 ≡ 1 ( m o d n ) \Rightarrow b \times b ^{n-2} \equiv 1\pmod{n} b×bn21(modn)
所以说,当n为质数时,b的乘法逆元为 x = b n − 2 ( m o d n ) x=b^{n-2}\pmod{n} x=bn2(modn)

#include <iostream>

using namespace std;

typedef long long LL;
int n;

void check(int a,int b,int p) {
    LL res = 1;
    while(b) {
        if(b & 1) res = (res * a) % p;
        b >>= 1;
        a = ((LL)a * a) % p;
    }
    
    cout << res << endl;
}

int main() {
    cin >> n;
    while( n --) {
        int a,p;
        cin >> a >> p;
        if(a % p == 0) puts("impossible");
        else check(a,p-2,p);
    }
    return 0;
}

扩展欧几里得算法

在这里插入图片描述

n n n不为质数时的情况

扩展欧几里得算法,用于求 a x + b y = gcd ⁡ ( a , b ) ax+by=\gcd(a,b) ax+by=gcd(a,b)的解
⇒ e x g c d ( a , b , x , y ) \Rightarrow exgcd(a,b,x,y) exgcd(a,b,x,y)

那么,当 b = = 0 b==0 b==0的时候, a x + b y = a ⇒ a x + b × 0 = a ax+by=a \Rightarrow ax+b \times 0 =a ax+by=aax+b×0=a

⇒ a x = a \Rightarrow ax=a ax=a

⇒ x = 1 , y = 0 \Rightarrow x=1 ,y = 0 x=1,y=0

b ! = 0 b!=0 b!=0的时候, a x + b y = gcd ⁡ ( a , b ) = gcd ⁡ ( b , a % b ) ax+by=\gcd(a,b)= \gcd(b,a\%b) ax+by=gcd(a,b)=gcd(b,a%b)

⇒ b x ′ + ( a % b ) y ′ = gcd ⁡ ( b , a % b ) \Rightarrow bx' + (a\%b)y'=\gcd(b,a\%b) bx+(a%b)y=gcd(b,a%b)

⇒ b x ′ + ( a − ⌊ a b ⌋ × b ) y ′ = gcd ⁡ ( b , a % b ) \Rightarrow bx' + (a - \left \lfloor \frac{a}{b} \right \rfloor \times b)y'=\gcd(b,a\%b) bx+(aba×b)y=gcd(b,a%b)

⇒ a y ′ + b ( x ′ − ⌊ a b ⌋ × y ′ ) = gcd ⁡ ( b , a % b ) = gcd ⁡ ( a , b ) \Rightarrow ay' + b(x' - \left \lfloor \frac{a}{b} \right \rfloor \times y')=\gcd(b,a\%b)=\gcd(a,b) ay+b(xba×y)=gcd(b,a%b)=gcd(a,b)

所以说,可以得到的结果是 x = y ′ , y = x ′ − ⌊ a b ⌋ × y ′ x=y',y = x' - \left \lfloor \frac{a}{b} \right \rfloor \times y' x=y,y=xba×y

#include <iostream>
using namespace std;
int n;

void exgcd(int a,int b,int& x,int& y) {
    if(!b) {
        x = 1, y = 0;
        return ;
    }
    int tx,ty;
    exgcd(b,a % b,tx,ty);
    x = ty, y = tx - a/b * ty;
}

int main() {
    cin >> n;
    while (n --) {
        int a,b,x,y;
        cin >> a >> b;
        
        exgcd(a,b,x,y);
        
        cout << x << " " << y << endl;
    }
    return 0;
}

线性同余方程

在这里插入图片描述
给定 n n n组数据 a i , b i , m i a_i,b_i,m_i ai,bi,mi,对于每组数求出一个 x i x_i xi,使其满足 a i × x i ≡ b i ( m o d m ) i a_i \times x_i≡b_i \pmod m_i ai×xibi(modm)i

经过变化后可以得出: a i × x i − m i × y i = b i a_i \times x_i -m_i \times y_i = b_i ai×ximi×yi=bi
⇒ a i × x i + m i × y i = b i \Rightarrow a_i \times x_i +m_i \times y_i = b_i ai×xi+mi×yi=bi

所以说,就可以使用扩展欧几里得算法求出 x i x_i xi的值,然后判断该等式方程是否存在解

该方程式存在解的充分必要条件是: b b b a a a m m m的最大公约数 d d d的倍数

那么,我们最后使用扩展欧几里得算法所求出的结果 x x x是基于 a a a m m m最大公约数的一个结果,想要求出和 b b b相关的结果,需要将 x x x扩大 b ÷ d b \div d b÷d
x = x × b ÷ d ( m o d m ) x = x \times b \div d \pmod m x=x×b÷d(modm)

#include <iostream>
using namespace std;
int n;
typedef long long LL;

int exgcd(int a,int b,int& x,int& y) {
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    int x1,y1;
    int ret = exgcd(b,a%b,x1,y1);
    x = y1;
    y = x1 - a / b * y1;
    return ret;
}

int main() {
    cin >> n;
    while(n --) {
        int a,b,m,x,y;
        cin >> a >> b >> m;
        int d = exgcd(a,m,x,y);
        if(b % d) puts("impossible");
        else {
            x = (LL)x * b / d % m;
            cout << x << endl;
        }
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/duchenlong/article/details/112534599

C++题解: 满足条件的01序列-爱代码爱编程

Catalan数 费马小定理 快速幂求逆元 题目描述 给定 n n n 个 0

蓝桥杯青少年创意编程大赛题解:循环嵌套-爱代码爱编程

题目描述 循环以及循环的嵌套,是同学们编写程序时常见的操作,如果用一对括号来代表一个循环的话那么三个循环出现的合法组合有 5 5 5 种,分别为∶ “{}{}{}”、"{{{}}}"、"{{}{

应用费马小定理快速求得大指数对p取模-爱代码爱编程

费马小定理(Fermat’s little theorem)是数论中的一个重要定理,在1636年提出。如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)。 快速幂超时 k = 998244353 def fpow(a, b): ans = 1 while b > 0: if b % 2

正态分布与泊松分布的关系-爱代码爱编程

正态分布 正态分布(normal distribution)又名高斯分布(Gaussian distribution)、正规分布,是一个非常常见的连续概率分布。正态分布在统计学上十分重要,经常用在自然和社会科学来代表一个不明的随机变量。 若随机变量X服从一个位置参数为 μ

信号处理学习笔记——傅里叶变换与希尔伯特变换-爱代码爱编程

傅里叶变换 傅立叶变换,表示能将满足一定条件的某个函数表示成三角函数(正弦和/或余弦函数)或者它们的积分的线性组合。 傅里叶认为**“任何”周期信号都可以表示为一系列成“谐波关系”的正弦信号的叠加** 常见例子:分解声音中的频率 时域→频域(去除噪音) 频域→时域(还原语音) a. 丢进去一个冰激凌(时域信号),就可以得到一个冰激凌配方(频域信号) —

复数的运算法则-爱代码爱编程

负数的运算包括加法法则,乘法法则,除法法则,开方法bai则,运算律,i的乘方法则等。具体运算方法如下: 1.加法法则 复数的加法法则:设z1=a+bi,z2=c+di是任意两个复数。两者和的实部是原来两个复数实部的和,它的虚部是原来两个虚部的和。两个复数的和依然是复数。即 2.乘法法则 复数的乘法法则:把两个复数相乘,类似两个多项式相乘,结果中

2020河南省CCPC A、C、E、I题解-爱代码爱编程

文章目录 A、班委竞选C、我得重新集结部队E、发通知I、太阳轰炸 题目链接: 2020年河南省CCPC大学生程序设计竞赛 A、班委竞选 #include<iostream> using namespace std; const int N = 55; int a[N][N]; int n,m; int main() {

剑指 Offer 16. 数值的整数次方 -- 快速幂-爱代码爱编程

0 题目描述 leetcode原题:剑指 Offer 16. 数值的整数次方 1 快速幂解法 快速幂实际上是二分思想的一种应用。 二分推导: x n

力扣LeetCode #50 Pow(x,n)(MyPow)-爱代码爱编程

- 题目描述 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 说明: -100.0 < x < 100.0 n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。 来源:LeetCode - 示例 示例 1: 输入: 2.00000, 10 输出: 1024.00000示例 2: 输入: 2.1000

剑指 Offer 16. 数值的整数次方-爱代码爱编程

这个问题毫无疑问应该用快速幂来做,不过问题在于考虑各种临界情况,比如 底数为0的情况,这里默认全部返回0指数为负数的情况指数太大越界情况,这里题目不要求考虑指数处于临界值的情况。这是个大坑,如 n =

快速幂模板-爱代码爱编程

递归版本 typedef long long ll; //求a^b%m得快速幂的递归写法 ll binaryPow(ll a,ll b,ll m) { if(b==0) return 1; //如果b为0,那么a^0=1; //b为奇数,转为b-1 if(b&1) //替换b%2==1,位与操作速度更快

斐波那契相乘(矩阵快速幂)-爱代码爱编程

牛客小白月赛20A 斐波那契 题目链接 算法分析 这里要用到一个结论就是斐波那契前n项平方和就是f[n]*f[n+1]结论证明比较好的矩阵快速幂的说明 算法实现 #include<iostream> #include<cstdio> #include<algorithm> #include<math.h&