头像

烟火流沙

中国矿业大学




在线 


活动打卡代码 AcWing 888. 求组合数 IV

烟火流沙
2小时前
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N=5010;

int primes[N],cnt;
//p的次数
int sum[N];
bool st[N];

//筛素数
void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])  primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)  break;
        }
    }
}

//get表示 n! 里面p的个数
int get(int n,int p)
{
    int res=0;
    while(n)
    {
        res+=n/p;
        n/=p;
    }
    return res;
}

//高精度乘法
vector<int>mul(vector<int>a,int b)
{
    vector<int>c;
    int t=0;
    for(int i=0;i<a.size();i++)
    {
        t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }

    //不是0的话,就把个位拿出来
    while(t)
    {
        c.push_back(t%10);
        t/=10;
    }
    return c;
}

int main()
{
    int a,b;
    cin>>a>>b;
    get_primes(a);

    //求p的次数
    for(int i=0;i<cnt;i++)
    {
        int p=primes[i];
        //当前这个数里面包含p的次数是多少
        sum[i]=get(a,p)-get(b,p)-get(a-b,p);
    }

    vector<int>res;
    res.push_back(1);

    for(int i=0;i<cnt;i++)
        for(int j=0;j<sum[i];j++)
            res=mul(res,primes[i]);

    for(int i=res.size()-1;i>=0;i--)    printf("%d",res[i]);
    puts("");
    return 0;
}



活动打卡代码 AcWing 887. 求组合数 III

烟火流沙
14小时前
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

int p;

int qmi(int a,int k)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}

int C(int a,int b)
{
    int res=1;
    //res*j/i
    for(int i=1,j=a;i<=b;i++,j--)
    {
        res=(LL)res*j%p;
        res=(LL)res*qmi(i,p-2)%p;
    }
    return res;
}

int lucas(LL a,LL b)
{
    if(a<p && b<p)  return C(a,b);
    return (LL)C(a%p,b%p)*lucas(a/p,b/p)%p;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        LL a,b;
        cin>>a>>b>>p;
        cout<<lucas(a,b)<<endl;
    }

    return 0;
}




活动打卡代码 AcWing 886. 求组合数 II

烟火流沙
15小时前
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N=100010,mod=1e9+7;

int fact[N],infact[N];

//利用逆元来求解组合数
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}

int main()
{
    fact[0]=infact[0]=1;
    //初始化,递归做法
    for(int i=1;i<N;i++)
    {
        fact[i]=(LL)fact[i-1]*i%mod;
        infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }

    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",(LL)fact[a]*infact[b]%mod*infact[a-b]%mod);
    }

    return 0;
}



活动打卡代码 AcWing 885. 求组合数 I

烟火流沙
16小时前
#include <iostream>
#include <algorithm>

using namespace std;

const int N=2010,mod=1e9+7;

int c[N][N];

void init()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(!j)  c[i][j]=1;  //边界,只选了一种结果,选1个苹果
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}

int main()
{
    init();
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",c[a][b]);
    }
    return 0;
}




#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N=110;
const double eps=1e-6;

int n;
//系数矩阵
double a[N][N];
//系数矩阵  结果  要化成 上三角矩阵!!!-----------


/*
    整体思路:
        1、找到当前绝对值最大的行
        2、将该行换到最上面
        3、从后往前,将该行第一个数变成1
        4、从后往前,将所有行的当前列消成0
*/
int gauss()
{
    //c表示枚举的哪一列,r表示枚举的哪一行
    int c,r;
    //按列枚举
    for(c=0,r=0;c<n;c++)
    {
        //1、从这一行开始,找到当前绝对值最大的这一行
        int t=r;
        for(int i=r;i<n;i++)
            if(fabs(a[i][c])>fabs(a[t][c]))
                t=i;

        //若第一列都为0,就继续寻找下一列
        if(fabs(a[t][c]) < eps)   continue;

        //2、换行处理
        for(int i=c;i<=n;i++)   swap(a[t][i],a[r][i]);
        //3、倒着来,从后面开始除,不然就把第一个数变成1,后面都就除以1了
        //   将当前这一行第一个数变为1,开始消元
        //   将每个系数都除以第一个数    
        for(int i=n;i>=c;i--)   a[r][i]/=a[r][c];
        //4、同样,也是倒着开始,将下面所有行的当前列消成0
        for(int i=r+1;i<n;i++)
            if(fabs(a[i][c])>eps)   //如果不是0,进行如下操作!!!
                for(int j=n;j>=c;j--)   
                    a[i][j]-=a[i][c]*a[r][j];    //都乘以相同的数 c列,把当前这一行变成0。

        //进行下一行
        r++;
    }   
    if(r<n)
    {
        //出现了0  非0 说明无解
        for(int i=r;i<n;i++)
            if(fabs(a[i][n])>eps)   //因为已经化成了上三角形式,所以只判断最后一行
                return 2;       //无解

        return 1;   //有无穷多组解
    }

    //倒着把方程消一遍,来求唯一解,倒着来后一行i借助于前一行j来进行消元
    //最后一列n就是答案!!!!!--------------------------------------
    //最后一行已经是最简的了
    for(int i=n-2;i>=0;i--)
        for(int j=i+1;j<n;j++)  // Xi -=系数 * Xj
            a[i][n]-=a[i][j]*a[j][n];//a[i][n]就是方程组的解,每一行根据最后一行进行消元
    return 0;   //唯一解
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n+1;j++)
            cin>>a[i][j];

    int t = gauss();
    //0表示唯一解,1表示无穷解,2表示无解

    if(t==0)
    {
        for(int i=0;i<n;i++)    printf("%.2lf\n",a[i][n]);
    }
    else if(t==1)   puts("Infinite group solutions");
    else puts("No solution");
    return 0;
}




#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    LL d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int main()
{
    int n;
    cin>>n;

    //用 bool变量 来表示当前是否无解
    bool has_answer=true;
    LL a1,m1;
    //先把第一个方程都进来
    cin>>a1>>m1;
    //再把后面的n-1个方程读进来
    for(int i=0;i<n-1;i++)
    {
        LL a2,m2;
        cin>>a2>>m2;

        //合并,首先用欧几里得算法求出方程k1*a1+m1=k2*a2+m2的系数k1,k2
        //上式化简为 k1*a1-k2*a2=m2-m1 => d
        LL k1,k2;
        //欧几里得算法求最大公约数
        LL d=exgcd(a1,a2,k1,k2);
        //有解的充要条件 (a1,a2)|m2-m1;---------------
        //余数不是0  则 无解
        if((m2-m1)%d)
        {
            has_answer = false;
            break;
        }
        //此时 有解,由上面注释可知,k1要变为 m2-m1 倍数关系,就要乘以 (m2-m1)/d
        k1*=(m2-m1)/d;
        // x = k1*a1+m1            通解为:{k1+k*a2/d
        //   = (k1+k*a2/d)*a1+m            {k2+k*a1/d            

        //把上式的系数  a2/d  存一下 
        LL t=a2/d;
        //把k1变成最小的 正整数 解
        k1=(k1%t+t)%t;

        //----x = a1*k1+m1+k*a1*a2/d = a1*k1+m1+k[a1,a2] 最终要变成 x = m+k*a;---------
        //m1就是x
        m1=a1*k1+m1;
        //求a1和a2的最小公倍数
        a1=abs(a1/d*a2);
    }
    if(has_answer)
    {
        //这里保证取余后一定是正数,+a1)%a1后一定是一个正数
        //题目答案求的就是 m%a1
        cout<<(m1%a1+a1)%a1<<endl;
    }
    else puts("-1");
    return 0;
}



活动打卡代码 AcWing 878. 线性同余方程

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

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

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b,m;
        scanf("%d%d%d",&a,&b,&m);
        int x,y;
        int d=exgcd(a,m,x,y);
        //b不是d的倍数,无解,其中d是(a,m)的最大公约数
        if(b%d) puts("impossible");
        //(a,m)|b; b整除(a,m)最大公约数
        //a*x+m*y=b;等式两边分别扩大b/d倍;即为
        //(a/d)*(a*x+m*y)=d  =>  最后要求的结果x即为  x*(b/d)%m;
        else printf("%d\n",(LL)x*(b/d)%m);
    }
    return 0;
}




#include <iostream>
#include <algorithm>

using namespace std;

//这里一定要加 引用符号&  不然 值传不回来
int exgcd(int a,int b,int &x,int &y)
{
    //return b?gcd(b,a%b):a;
    if(!b)
    {
        //b=0时,x=1,y=0是一组解
        x=1,y=0;
        return a;
    }
    //记下最大公约数
    int d = exgcd(b,a%b,y,x);
    //递归运算
    //a*x+b*(y-a/b*x)=d;x不变,y=y-a/b*x;
    y-=a/b*x;
    return d;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b,x,y;
        scanf("%d%d",&a,&b);

        //系数用引用来传
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}



活动打卡代码 AcWing 876. 快速幂求逆元

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

// a^k % p
int qmi(int a,int k,int p)
{
    //定义一个答案
    int res=1;
    //本质上求k的二进制表示
    while(k)
    {
        //a是不断变化反复平方的;如果当前末位是1的话,就执行下面语句
        if(k&1) res = (LL)res*a%p;
        //算完之后,把a的末位删掉
        k >>= 1;
        //下一个数是上一个数的平方,就是不断平方即可
        a = (LL)a*a%p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,p;
        scanf("%d%d",&a,&p);

        //求逆元,由费马定理知,本质上是求a^(p-2)
        int res=qmi(a,p-2,p);
        //无解,a是p的倍数,a%p不等于0,就不是倍数关系
        if(a%p) printf("%d\n",res);
        else puts("impossible");
    }

    return 0;
}



活动打卡代码 AcWing 875. 快速幂

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

// a^k % p
int qmi(int a,int k,int p)
{
    //定义一个答案
    int res=1;
    //本质上求k的二进制表示
    while(k)
    {
        //a是不断变化反复平方的;如果当前末位是1的话,就执行下面语句
        if(k&1) res = (LL)res*a%p;
        //算完之后,把a的末位删掉
        k >>= 1;
        //下一个数是上一个数的平方,就是不断平方即可
        a = (LL)a*a%p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,k,p;
        scanf("%d%d%d",&a,&k,&p);

        // a^k % p
        printf("%d\n",qmi(a,k,p));
    }

    return 0;
}