投稿
  1. 高性能架构探索首页
  2. C/C++

数学

admin • • C/C++ • 阅读 224

快速幂:P1226（注：2的31次方是2147483648，2的32次方是4294967296，int：4字节，8位，32比特，最大2147483647）

//c/c++ compile run 插件中设置external terminnal,f6运行
#include <iostream>
int f(long long a,long long b,long long p){
    long res = 1;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
using namespace std;
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    long long a,b,p;
    cin >> a >> b >> p;
    printf("%lld^%lld mod %lld=%lld",a,b,p,f(a,b,p));
    return 0;
}

数学数学

高精度+快速幂：P1045

计算位数：数学

 

//c/c++ compile run 插件中设置external terminnal,f6运行
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
const int N = 500;
#define VI vector<int>
int p;
VI res(N), a(N);
VI mul(VI &a,VI &b){
    VI t(N);
    for(int i=0;i<N;i++){
        for(int j=0;j+i<N;j++){
            t[i+j]+=a[i]*b[j];
            if(i+j+1<N)t[i+j+1]+=(t[i+j]/10);
            t[i+j]%=10;
        }
    }
    return t;
}
void f(int p){
    a[0]=2,res[0]=1;
    while(p){
        if(p&1)res=mul(res,a);
        a=mul(a,a);
        p>>=1;
    }
    res[0]--;
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin>>p;
    f(p);
    cout << 1+int(p*log(2)/log(10)) << endl;
    for(int i=9;i>=0;i--){
        for(int j=49;j>=0;j--){
            cout << res[i*50+j];
        }
        cout << endl;
    }
    return 0;
}

 如何对矩阵做快速幂运算：洛谷P3390

#include <iostream>
#include <string.h>
using namespace std;
const int N=105;
const int mod=1000000007;
long long n,m;
struct matrix{
    long long c[N][N];
    matrix(){memset(c,0,sizeof(c));}
}res,A;
matrix operator*(matrix&a,matrix&b){
    matrix t;
    for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
            for(int j=1;j<=n;j++)
                t.c[i][j]=(t.c[i][j]+a.c[i][k]*b.c[k][j])%mod;
    return t;
}
void qpow(){
    while(m){
        if(m&1)res=res*A;
        A=A*A;
        m>>=1;
    }
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>A.c[i][j];
    for(int i=1;i<=n;i++)res.c[i][i]=1;
    qpow();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){cout<<res.c[i][j];if(j!=n)cout<<' ';}
        if(i!=n)cout<<endl;
    }
    return 0;
}

 矩阵加速递推：从O(N)变成O(logN)，洛谷P1962，洛谷P1939

数学

//P1962
#include <iostream>
#include <string.h>
using namespace std;
const int mod=1000000007;
struct matrix{
    long long c[3][3];
    matrix(){memset(c,0,sizeof(c));}
}res,f;
matrix operator*(matrix&x,matrix&y){//为什么这里的返回值不能是引用类型：废话，t是个临时值，临时值会被消灭掉
    matrix t;
    for(int i=1;i<=2;i++)
        for(int k=1;k<=2;k++)
            for(int j=1;j<=2;j++)
                t.c[i][j]=(t.c[i][j]+x.c[i][k]*y.c[k][j]%mod)%mod;
    return t;
}
// class matrix{
// public:
//     long long c[3][3];
//     matrix(){memset(c,0,sizeof(c));}
//     matrix operator*(matrix&x){
//         matrix t;
//         for(int i=1;i<=2;i++)
//             for(int k=1;k<=2;k++)
//                 for(int j=1;j<=2;j++)
//                     t.c[i][j]=(t.c[i][j]+((*this).c[i][k]*x.c[k][j])%mod);
//         return t;
//     }
//     // matrix& operator*=(matrix&x){
//     //     return (*this)=(*this)*x;
//     // }
//     void operator=(matrix&x){
//         for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)(*this).c[i][j]=x.c[i][j];
//     }//赋值构造函数？
// };
// matrix res,f;
long long qpow(long long m){
    while(m){
        if(m&1)res=res*f;
        f=f*f;
        m>>=1;
    }
    return res.c[1][1];
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    long long n;
    cin>>n;
    if(!n){
        cout<<0;
        return 0;
    }
    res.c[1][1]=1;
    f.c[1][1]=f.c[1][2]=f.c[2][1]=1;
    cout<<qpow(n-1);
    return 0;
}
// 1 1 1 1
// 1 0 1 0
// 2 1
// 1 1

View Code

数学

//P1939,构造三阶矩阵
#include <iostream>
#include <string.h>
using namespace std;
const int mod=1000000007;
struct matrix{
    long long c[4][4];
}res,f;
matrix operator*(matrix&x,matrix&y){//为什么这里的返回值不能是引用类型：废话，t是个临时值，临时值会被消灭掉
    matrix t;
    memset(t.c,0,sizeof(t.c));
    for(int i=1;i<=3;i++)
        for(int k=1;k<=3;k++)
            for(int j=1;j<=3;j++)
                t.c[i][j]=(t.c[i][j]+x.c[i][k]*y.c[k][j]%mod)%mod;
    return t;
}
long long qpow(long long m){
    while(m){
        if(m&1)res=res*f;
        f=f*f;
        m>>=1;
    }
    return res.c[1][1];
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        if(n<4){
            cout<<1<<endl;
            continue;
        }
        memset(res.c,0,sizeof(res.c));
        memset(f.c,0,sizeof(f.c));
        res.c[1][1]=res.c[1][2]=res.c[1][3]=1;
        f.c[1][1]=f.c[1][2]=f.c[2][3]=f.c[3][1]=1;
        cout<<qpow(n-3)<<endl;
    }
    return 0;
}

View Code

 欧几里得算法求gcd,lcm，洛谷P1092

数学

数学

数学

#include <iostream>
using namespace std;
int x,y,cnt;
int gcd(int a,int b){
    while(a%b){
        int t2=a%b;
        a=b,b=t2;
    }
    return b;
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin>>x>>y;
    int t=x*y;
    //p*q==x*y
    for(int p=x;p*p<=t;p++){
        int q=t/p;
        if(gcd(q,p)==x&&p*q==t)cnt+=2;
    }
    if(x==y)cnt--;
    cout<<cnt;
    return 0;
}

View Code

质数筛，洛谷P5736.注：1不是质数。

数学

#include <iostream>
using namespace std;
int n,a[105];
bool is_pri(int x){
    if(x==1)return false;
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return false;
    }
    return true;
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        if(is_pri(a[i]))cout<<a[i]<<' ';
    }
    return 0;
}

View Code

质因数分解：P2043.（用到算术基本定理，又称唯一分解定理；以及n的超过根号n的因数最多一个）

数学

#include <iostream>
using namespace std;
int n,a[10005];
void f(int x){
    for(int i=2;i<=x/i;i++){
        while(x%i==0){
            a[i]++;
            x/=i;
        }    
    }
    if(x!=1)a[x]++;
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin>>n;
    for(int i=2;i<=n;i++)f(i);
    for(int i=1;i<=n;i++)if(a[i])cout<<i<<' '<<a[i]<<endl;
    return 0;
}

View Code

 筛法求质数：埃氏筛法，洛谷P3383

数学

#include <iostream>
using namespace std;
int n,q,k,a[100000005],cnt;
bool no[100000005];
void f(){
    for(long long i=2;i<=n;i++){
        long long j=i;
        if(!no[j]){
            a[++cnt]=i;
            for(j=i*i;j<=n;j+=i)no[j]=true;
        }
    }
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin>>n>>q;
    f();
    while(q--){
        cin>>k;
        cout<<a[k]<<endl;
    }
    return 0;
}

View Code

欧拉筛法：O(N)，省略了埃氏筛法中重复筛去质数的时间，必须掌握；

数学

#include <iostream>
using namespace std;
int n,q,k,a[100000005],cnt;
bool no[100000005];
void f(){
    for(long long i=2;i<=n;i++){
        long long j=i;
        if(!no[j]){
            a[++cnt]=i;
            for(j=i*i;j<=n;j+=i)no[j]=true;
        }
    }
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin>>n>>q;
    f();
    while(q--){
        cin>>k;
        cout<<a[k]<<endl;
    }
    return 0;
}

View Code

 

原文链接: https://www.cnblogs.com/-ark/p/17053351.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

    数学

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/312342

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月16日 下午12:21
下一篇 2023年2月16日 下午12:21

相关推荐