AcWing算法提高课数学部分

本文主要是介绍AcWing算法提高课数学部分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

筛质数

1.196. 质数距离 - AcWing题库

思路：素数筛+离散化

1）看题目就知道要用到素数筛

2）其中有一个结论：1-r之间的素数不超过sqrt(r)

3）l~r的区间数字太大，但是r-l并不是很大，就转换成0~l-r

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
const int maxn = 5e4+10;;
const int maxx=1e6+10;
bool vis[maxn]; // 0 为素数 1 为非素数
int tot, phi[maxn], prime[maxn];
int num[maxx]={0};
void CalPhi() {
    vis[1] = 1, phi[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) prime[tot++] = i, phi[i] = i - 1;
        for (int j = 0; j < tot; ++j) {
            if (i * prime[j] > maxn) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
int p[maxx]={0};
signed main(void){
    CalPhi();
    int a,b;
    while(~scanf("%lld %lld",&a,&b)){
        memset(num,0,sizeof num);
        memset(p,0,sizeof p);
        for(int i=0;i<tot;i++){
            if(prime[i]>=b){
                break;
            }
            for(int j=a/prime[i];j*prime[i]<=b;j++){
                if(j<2){
                    continue;
                }
                num[j*prime[i]-a]++;
            }
        }
        int minn=0,maxp=0;
        int flag=0;
        for(int j=0;j<=b-a;j++){
            if(num[j]==0&&j+a>1){
                p[flag++]=j+a;
            }
        }

        for(int i=1;i+1<flag;i++){
            if(p[i+1]-p[i]>p[maxp+1]-p[maxp]) maxp=i;
            if(p[i+1]-p[i]<p[minn+1]-p[minn]) minn=i;
        }
        if(flag<2){
            printf("There are no adjacent primes.\n");
        }else{
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",p[minn],p[minn+1],p[maxp],p[maxp+1]);
        }

    }
}

分解质因数

1.197. 阶乘分解 - AcWing题库

思路：

1）打素数表

2）当我们算一个素数i的含有多少个的时候，拆分成计算1-n中的数中有多个数有i，i^2，i^3…，当然我们计算的时候，计算含有这个素数的个数的时候要按照上面样例中求2的方式求，就是横着求，才能够缩短时间复杂度

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 10000001;
bool vis[maxn]; // 0 为素数 1 为非素数
int tot, phi[maxn], prime[maxn];

void CalPhi() {
    vis[1] = 1, phi[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) prime[tot++] = i, phi[i] = i - 1;
        for (int j = 0; j < tot; ++j) {
            if (i * prime[j] > maxn) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
int p[maxn]={0};
int main(){
    int n;
    scanf("%d",&n);
    CalPhi();
    int flag=0;
    for(int i=2;i<=n;i++){
        if(vis[i]==0){
            flag=0;
            int s=n;
            int now;
            while(s){
                flag+=s/i;
                s/=i;
            }
            printf("%d %d\n",i,flag);
        }
    }
}

快速幂

1.1290. 越狱 - AcWing题库

思路：补集

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define int long long
const int mod=100003;
inline long long Pow(long long a, long long n, long long m) {
    long long t = 1;
    for (; n; n >>= 1, a = (a * a % m))
        if (n & 1) t = (t * a % m);
    return t % m;
}

signed main(void){
    int n,m;
    scanf("%lld %lld",&m,&n);//不越狱m m-1 m-1 ……  总：m*m*m*m*……
    printf("%lld\n",(Pow(m,n,mod)%mod-m*Pow(m-1,n-1,mod)%mod+mod)%mod);

}

约数个数

1.1294. 樱花 - AcWing题库

思路：主要是公式推导，最后推到成看(n!)^2的约数个数（推倒思路见前文章）

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int maxx=1e6+10;//约数个数 横向求解的过程
const int maxn = 10000001;
const int mod=1e9+7;
bool vis[maxn]; // 0 为素数 1 为非素数
int tot, phi[maxn], prime[maxn];

void CalPhi() {
    vis[1] = 1, phi[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) prime[tot++] = i, phi[i] = i - 1;
        for (int j = 0; j < tot; ++j) {
            if (i * prime[j] > maxn) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
int p[maxx]={0};
int main(){
    int n;
    scanf("%d",&n);
    CalPhi();
    long long int s=1;
    for(int i=0;i<tot;i++){
        if(prime[i]<=n){
            int now=n;
            int flag=0;
            while(now){
                flag+=now/prime[i];
                now/=prime[i];
            }
            flag*=2;
            flag%=mod;
            s*=flag+1;
            s%=mod;
            
        }
    }
    printf("%lld\n",s);
}

2.198. 反素数 - AcWing题库

思路：AcWing 198. 反素数 - AcWing（三个结论）

1）1~n中最大的反质数就是1~n中约数个数最多的数中最小的一个

2）1~n中任何数的不同质因子都不会超过10个，因为2*3*5*7*11*13*17*19*23*29*31>2*10^9，且所有质因数的指数总和不超过30，因为2^31>2e9

3）x的质因数是连续的若干最小的质数，且质数的质数单调递减。如果不连续，例如选择3 7不如选择相同指数个数的2 3，这样的数更小。指数的问题就是，如果质数前面的大后面的小，两者指数交换，得到的数肯定比这个数小

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define int long long
int prime[15]={0,2,3,5,7,11,13,17,19,23,29};
int s_cnt=1e9+1,s_num=1;
int c[15];
int n;
void dfs(int now,int cnt,int num){//现在到了哪一个 现在的乘积，现在的约数个数
    if(now==11){
        if((num>s_num)||(cnt<s_cnt&&num==s_num)){
            s_num=num;
            s_cnt=cnt;
        }
        return;
    }
    int now_cnt=cnt;//现在的乘积
    for(int i=0;i<=c[now-1];i++){
        if(now_cnt>n){
            return;
        }
        c[now]=i;
        dfs(now+1,now_cnt,num*(i+1));
        now_cnt*=prime[now];
    }
}
signed main(void){
    scanf("%lld",&n);
    c[0]=2e9;
    dfs(1,1,1);
    printf("%lld\n",s_cnt);
}

结论：

欧拉函数

1.220. 最大公约数 - AcWing题库

思路：AcWing 220. 最大公约数(通俗易懂&效率高) - AcWing

主要是转换，通过gcd(x*d,y*d)=d，转换为找gcd(x,y)=1的总数，这样的话先打素数表，再去求欧拉函数的和（为了减少时间复杂度，也可以先利用前缀和进行欧拉函数的求和）

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define int long long
const int maxn = 10000001;
bool vis[maxn]; // 0 为素数 1 为非素数
int tot, phi[maxn], prime[maxn];

void CalPhi() {
    vis[1] = 1, phi[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) prime[tot++] = i, phi[i] = i - 1;
        for (int j = 0; j < tot; ++j) {
            if (i * prime[j] > maxn) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
signed main(void){
    int n;
    scanf("%lld",&n);
    CalPhi();
    int sum=0;
    for(int i=0;i<tot;i++){
        if(prime[i]<=n){
            int flag=0;
            for(int j=2;j<=n/prime[i];j++){
                flag+=phi[j];
            }
            flag*=2;
            sum+=flag+1;//算上a=b,且为素数
        }

    }
    printf("%lld\n",sum);
}

这篇关于AcWing算法提高课数学部分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！