头像

霜满地

不必在乎别人的看法。




离线:10小时前


最近来访(58)
用户头像
kumo
用户头像
TMJYH09
用户头像
Dumhdurum
用户头像
acwing_3271
用户头像
Wudiy
用户头像
ingx
用户头像
半瓶可乐
用户头像
VegeDog
用户头像
可爱的软泥怪
用户头像
xuekedou
用户头像
PlusFly
用户头像
NULL_32
用户头像
时光中有你
用户头像
evecome
用户头像
每天学什么QAQ
用户头像
林大B
用户头像
wyzde18
用户头像
outlier_3
用户头像
海_5
用户头像
ZengYongRui

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

#include <iostream>
using namespace std;
typedef long long LL;

LL 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;
    cin >> n;
    while(n--)
    {
        int a, b, m , x, y;
        cin >> a >> b >> m;
        int d = exgcd(a, m, x, y);
        if(b % d) cout << "impossible" << endl;
        else cout << (LL) x * b / d % m << endl;
    }

    return 0;
}



#include <iostream>
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;
    cin >> n;
    while(n--)
    {
        int a, b, x, y;
        cin >> a >> b;

        exgcd(a, b, x, y);

        cout << x << " " << y << endl;
    }
    return 0;
}



#include <iostream>
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;
    cin >> n;
    while(n--)
    {
        int a, b, x, y;
        cin >> a >> b;

        exgcd(a, b, x, y);

        cout << x << " " << y << endl;
    }
    return 0;
}


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

#include <iostream>
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 = (LL) a * a % p;
        b >>= 1;
    }

    return res;
}


int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a, p;
        cin >> a >> p;
        int t = qmi(a, p - 2, p);
        if(a % p) cout << t << endl;
        else cout << "impossible" << endl;
    }

    return 0;
}



#include <iostream>
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 = (LL) a * a % p;
        b >>= 1;
    }

    return res;
}


int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a, p;
        cin >> a >> p;
        int t = qmi(a, p - 2, p);
        if(a % p) cout << t << endl;
        else cout << "impossible" << endl;
    }

    return 0;
}



#include <iostream>
using namespace std;
const int N = 1000010;
int phi[N], cnt;
bool st[N];
int primes[N];

void get_phi(int n)
{
    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++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }

            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}

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

    get_phi(n);

    long long res = 0;

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

    cout << res << endl;

    return 0;
}



#include <iostream>
using namespace std;
const int N = 1000010;
int phi[N], cnt;
bool st[N];
int primes[N];

void get_phi(int n)
{
    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++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }

            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}

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

    get_phi(n);

    long long res = 0;

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

    cout << res << endl;

    return 0;
}



#include <iostream>
using namespace std;

int oula(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 << oula(x) << endl;
    }
    return 0;
}


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

#include <iostream>
using namespace std;

int oula(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 << oula(x) << endl;
    }
    return 0;
}


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

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }
    return 0;
}