题目描述

blablabla

样例

#include<iostream>
using namespace std;
const int N = 1e5 + 10;


int q[N];

void quick_sort(int q[], int l, int r) {
    // 边界条件
    if (l >= r) return;

    // 双指针移动
    int i = l - 1, j = r + 1; 
    int mid = q[l + r >> 1];
    while (i < j) {
        do i++; while(q[i] < mid);
        do j--; while(q[j] > mid);
        if (i < j) swap(q[i], q[j]);
    }
    // i 左边的数一定 <= mid
    // j 右边的数一定 >= mid
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}


int main(){
    // 输入
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &q[i]);
    }

    // 排序
    quick_sort(q, 0, n - 1);

    // 输出
    for (int i = 0; i < n; i++) {
        printf("%d ", q[i]);
    }
    return 0;


}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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;
        b >>= 1;
        a = a * (LL)a % p;
    }
    return res;
}


int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int a, p;
        // 注意输入输出
        scanf("%d%d", &a, &p);
        if (a % p == 0) cout << "impossible" << endl;
        else printf("%lld\n", qmi(a, p - 2, p));
    }
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        // 一开始是 a
        if (k & 1) res = (LL)res * a % p;
        // 删去 k 的末位
        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);
        printf("%d\n", qmi(a, k, p));
    }
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int primes[N], cnt;
int phi[N];
bool st[N];

void get_eulers(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)
            {
                // pj * i 的质因子 和 i 的质因子相同
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            // pj * i 的质因子 比 i 的质因子多了 pj
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }

}

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

    get_eulers(n);

    LL res = 0;
    for (int i = 1; i <= n; i++) res += phi[i];
    printf("%lld\n", res);
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>

using namespace std;

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i++)
    {
        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;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<unordered_map>


using namespace std;

typedef long long LL;

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


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

    unordered_map<int, int> primes;

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

        // 把因子 i 的个数统计清楚
        for (int i = 2; i <= x / i; i++)
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i]++;
            }


        }

        if (x > 1) primes[x]++;
    }

    LL res = 1;

    for (auto it : primes) res = res * (it.second + 1) % mod;
    cout << res << endl;
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<bits/stdc++.h>

using namespace std;

int n, a, b;

int gcd(int x, int y)
{
    if (x % y == 0) return y;
    return gcd(y, x % y);
}

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

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

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

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

    unordered_map<int, int> primes;

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

        for (int i = 2; i <= x / i; i++)
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i]++;
            }
        }

        if (x > 1) primes[x]++;
    }

    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b--) t = (t * a + 1) % mod;
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<unordered_map>


using namespace std;

typedef long long LL;

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


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

    unordered_map<int, int> primes;

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

        // 把因子 i 的个数统计清楚
        for (int i = 2; i <= x / i; i++)
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i]++;
            }


        }

        if (x > 1) primes[x]++;
    }

    LL res = 1;

    for (auto it : primes) res = res * (it.second + 1) % mod;
    cout << res << endl;
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int n;

void get_divisors(int n)
{
    vector<int> res;

    for (int i = 1; i <= n / i; i++){

        if (n % i == 0){
            res.push_back(i);

            if (i != n / i){
                res.push_back(n / i);
            }
        }
    }
    sort(res.begin(), res.end());
    for (auto item : res){
        cout << item << " ";
    }
    puts("");
}

int main()
{
    cin >> n;
    while(n--){
        int x;
        cin >> x;
        get_divisors(x);
    }
    return 0;
}