头像

BlackAjactic




离线:3小时前


最近来访(96)
用户头像
greg666
用户头像
StkOvflow
用户头像
有机物
用户头像
不高兴的兽奶
用户头像
TKater_yzt
用户头像
mp4
用户头像
yxc的小迷妹
用户头像
hncsxzx
用户头像
SilenceLamb.
用户头像
种花家的市长
用户头像
是一个一个一个CE自动机啊啊啊啊啊啊啊啊啊啊啊啊啊
用户头像
Cosys
用户头像
情断青丝
用户头像
ocean2008
用户头像
睡觉_67
用户头像
incra
用户头像
Ju_1
用户头像
潘潘_the_panda
用户头像
violet_garden
用户头像
馨月

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

BlackAjactic
1个月前
#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;
}



BlackAjactic
1个月前
#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 876. 快速幂求逆元

BlackAjactic
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

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

int main () {
    int n;
    cin >> n;
    while (n--) {
        int a, m;
        cin >> a >> m;
        if (a % m)
            cout << qpow(a, m - 2, m) << endl;
        else
            puts("impossible");
    }
}


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

BlackAjactic
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

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

int main () {
    int n;
    cin >> n;
    while (n--) {
        int a, m;
        cin >> a >> m;
        if (a % m)
            cout << qpow(a, m - 2, m) << endl;
        else
            puts("impossible");
    }
}


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

BlackAjactic
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

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

int main () {
    int n;
    cin >> n;
    while (n--) {
        int a, b, m;
        cin >> a >> b >> m;
        cout << qpow(a, b, m) << endl;
    }
}



BlackAjactic
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 1001000;
int primes[N], phi[N], cnt; 
bool st[N];

LL get (int n) {
    LL res = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }

        for (int j = 0; primes[j] <= n / i; j++) {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0) {
                phi[t] = phi[i] * primes[j];
                break;
            } else {
                phi[t] = phi[i] * (primes[j] - 1);
            }
        }
    }

    for (int i = 1; i <= n; i++)
        res += phi[i];
    return res;
}

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

    cout << get(n) << endl;
}


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

BlackAjactic
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

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

    while (n--) {
        int a;
        cin >> a;

        long long res = a;
        for (int i = 2; i <= a / i; i++) {
            if (a % i == 0) {
                res = res * (i - 1) / i;
                while (a % i == 0)
                    a /= i;
            }
        }
        if (a > 1)
            res = res * (a - 1) / a;

        cout << res << endl;
    }
}


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

BlackAjactic
1个月前
#include <unordered_map>
#include <iostream>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;

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

    unordered_map<int, int> primes;
    while (n--) {
        int a;
        cin >> a;

        for (int i = 2; i <= a / i; i++)
            while (a % i == 0)
                a /= i, primes[i]++;
        if (a > 1)
            primes[a]++;
    }

    long long res = 1;
    for (auto prime : primes) {
        long long t = 1;
        int p = prime.first, q = prime.second;
        while (q--)
            t = (t * p + 1) % MOD;
        res = res * t % MOD;
    }

    cout << res << endl;
}


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

BlackAjactic
1个月前
#include <unordered_map>
#include <iostream>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;

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

    unordered_map<int, int> primes;
    while (n--) {
        int a;
        cin >> a;

        for (int i = 2; i <= a / i; i++)
            while (a % i == 0)
                a /= i, primes[i]++;
        if (a > 1)
            primes[a]++;
    }

    long long res = 1;
    for (auto prime : primes)
        res = res * (prime.second + 1) % MOD;

    cout << res << endl;
}


活动打卡代码 AcWing 417. 不高兴的津津

BlackAjactic
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10;
int res, maxn;

int main () {
    for (int i = 1; i <= 7; i++) {
        int a, b;
        cin >> a >> b;
        if (a + b > 8 && a + b > maxn)
            res = i, maxn = a + b;
    }
    cout << res << endl;
}