头像

Struggle

acwing


访客:11187

离线:3小时前


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

Struggle
9小时前
#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);
    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);
        if (b % d) puts("impossible");
        else printf("%d\n", (LL)b / d * x % m);
    }

    return 0;
}





Struggle
9小时前
#include <iostream>
#include <algorithm>

using namespace std;

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);
    y -= a / b * x;
    return d;
}

int main()
{
    int n;
    scanf("%d", &n);

    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int x, y;
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }

    return 0;
}



活动打卡代码 AcWing 89. a^b

Struggle
14小时前
#include<iostream>
typedef long long LL;
using namespace std;
LL quick_pow(LL a,int b,int p)
{
    LL res=1%p;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int main()
{
    int a,b,p;
    cin>>a>>b>>p;
    cout<<quick_pow(a,b,p);
    return 0;
}


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

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


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


int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }

    return 0;
}



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

#include<iostream>
typedef long long LL;
using namespace std;
LL quick_pow(LL a,LL b,LL p)
{
    LL res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,p;
        cin>>a>>b>>p;
        cout<<quick_pow(a,b,p)<<endl;
    }
}



#include<iostream>
using namespace std;
typedef long long LL;
const int N=1e6+10;
//euler[N]代表N的欧拉函数 st[N]=true;代表N为素数(质数) 
//prime数组从小到大存储n的质因数
int euler[N],st[N],idx,prime[N];
void euler_sum(int n)
{
    euler[1]=1;
    for(int i=2;i<=n;i++)//求euler[2],euler[3],euler[4]....euler[n];
    {
        if(!st[i])
        {
            prime[idx++]=i;
            euler[i]=i-1;//可根据质数的定义
        }
        for(int j=0;prime[j]<=n/i;j++)
        {
            int t=prime[j]*i;
            st[t]=true;
            if (i % prime[j] == 0)
            {
                euler[t] = euler[i] * prime[j];
                break;
            }
            euler[t] = euler[i] * (prime[j] - 1);
        }
    }
}
int main()
{
    int n;
    cin>>n;
    euler_sum(n);
    LL res=0;
    for(int i=1;i<=n;i++) res+=euler[i];
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 873. 欧拉函数

#include <iostream>

using namespace std;


int phi(int 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);

    return res;
}


int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        cout << phi(x) << endl;
    }

    return 0;
}



活动打卡代码 AcWing 872. 最大公约数

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    return a%b?gcd(b,a%b):b;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
}



活动打卡代码 AcWing 871. 约数之和

#include<iostream>
#include<cmath>
#include<unordered_map>
using namespace std;
int mod=1e9+7;
int main()
{
    int n;
    unordered_map<int,int> q;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        for(int i=2;i<=a/i;i++)
        {
            while(a%i==0)
            {
                a/=i;
                q[i]++;
            }
        }
        if(a>1) q[a]++;
    }
    long long res=1;
    for(auto t:q)
    {
        int radix=t.first,exp=t.second;
        long long o=1;
        while(exp--)
            o=(o*radix+1)%mod;
        res=res*o%mod;
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 870. 约数个数

#include<iostream>
#include<unordered_map>
int mod=1e9+7;
typedef long long LL;
using namespace std;
int main()
{
    int n;
    unordered_map<int,int> q;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        for(int i=2;i<=a/i;i++)
            while(a%i==0)
                a/=i, q[i]++;
        if(a>1) q[a]++;
    }
    LL res=1;
    for(auto t:q) res=res*(t.second+1)%mod;
    cout<<res;
    return 0;
}