头像

alin




离线:17小时前


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

alin
8个月前
#include <iostream>
#include <algorithm>

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;
        printf("%d\n", gcd(a, b));
    }
    return 0;
}


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

alin
8个月前
#include <iostream>
#include <algorithm>
#include <unordered_map> 

using namespace std;

typedef long long LL;

const int mod = 1e9+7;
int main()
{

    unordered_map<int, int> primes;
    int n ;
    cin>>n;
    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 prime : primes)
    {
        int p = prime.first, a = prime.second;

        LL t = 1;
        while(a --)
            t = ( t * p +1) % mod; // t =1, t*p+1 = p+1, (p+1)*p+1 = p^2 + p +1 .....
        res = (res * t) % mod;
    }


    cout<<res<<endl;
    return 0;


}


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

alin
8个月前
#include <iostream>
#include <algorithm>
#include <unordered_map> 

using namespace std;

typedef long long LL;

const int mod = 1e9+7;
int main()
{

    unordered_map<int, int> primes;
    int n ;
    cin>>n;
    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 prime : primes)  res = res *( prime.second +1) % mod;
    cout<<res<<endl;
    return 0;


}


活动打卡代码 AcWing 869. 试除法求约数

alin
8个月前
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

vector<int> 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());
    return res;
}

int main()
{
    int n;
    cin>>n;
    while(n --)
    {
        int x;
        cin>>x;
        auto res = get_divisors(x);
        for(auto i:res) cout<<i<<' ';
        cout<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 868. 筛质数

alin
8个月前
#include <iostream>
#include<algorithm>

using namespace std;

const int N = 1000010;
int cnt, prime[N];
bool st[N];

void get_prime(int n)
{
    for(int i =2; i <= n; i++)
    {
        if(!st[i])
        {
            prime[cnt++] = i;
            for(int j = i+i; j<=n; j+=i) st[j] = true;
        }
    }
}

int main()
{
    int n;
    cin>>n;
    get_prime(n);
    printf("%d\n", cnt);
    return 0;

}

线性筛法

#include <iostream>
#include<algorithm>

using namespace std;

const int N = 1000010;
int cnt, prime[N];
bool st[N];

void get_prime(int n)
{
    for(int i =2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= n/i; j++)
        {
            st[prime[j] *i ] = true;
            if(i % prime[j] == 0)  break; // prime[j]一定是i的最小质因子
        }
    }
}

int main()
{
    int n;
    cin>>n;
    get_prime(n);
    printf("%d\n", cnt);
    return 0;

}


活动打卡代码 AcWing 867. 分解质因数

alin
8个月前
#include<iostream>
#include<algorithm>

using namespace  std;

void divide(int n)
{
    for(int i = 2; i <= n /i; i++)
    {
        while(n % i == 0)
        {
            int s = 0;
            while(n % i == 0)
            {
                n /= i;
                s++;
            }
            printf("%d %d \n", i, s );
        }
    }
    if(n > 1) printf("%d %d \n", n, 1); // 因为只有一个大于sqrt(n)的质因子  要想减少搜索区间到sqrt(n) 当最后n>1时候 n就是
    puts("");
}

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




alin
8个月前
#include <iostream>
#include <cstdio>

using namespace std;

int n;


bool is_prime(int n )
{
    if(n <2) return false;
    for(int i = 2; i<= n /i; i++)
    {
        if(n % i == 0) return false;
    }
    return true;
}

int main()
{
    cin>>n;
    for(int i = 0; i<n; i++)
    {
        int x;
        cin>>x;
        if(is_prime(x)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}



alin
8个月前
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || p == root || q == root) return root;

        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);

        if(left &&  right) return root;
        return left?left:right;
    }
};



alin
8个月前
class Solution {
public:
    int strToInt(string str) {
        int n = str.size();
        int k = 0;
        long long number = 0;
        int flag = 1;

        while(k<n && str[k] == ' ') k ++;

        if(str[k] == '+') k++;
        else if(str[k] == '-') { flag *= -1; k ++;}

        while(k < n && str[k] >= '0' &&  str[k] <= '9')
        {
            number = number * 10 + (str[k] - '0');
            k ++;
        }

        number *= flag;
        if(number > INT_MAX) return INT_MAX;
        if(number < INT_MIN) return INT_MIN;
        return (int)number;
    }
};


活动打卡代码 AcWing 86. 构建乘积数组

alin
8个月前
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        vector<int> left(n, 1); // 左右边界的话应该是1
        vector<int> right(n, 1);

        for(int i = 1; i < n; i++)
            left[i] = left[i -1] * A[i -1]; 

        for(int i = n -2; i>= 0; i --)
            right[i] = right[i+1] * A[i+1];

        vector<int> B(n, 0);
        for(int i = 0; i<n; i++) B[i] = left[i] * right[i];
        return B;

    }
};