• 个人简介

    一、数论

    1.分解质因数


    int n; //需要分解的数
    int cnt; // 计数器
    int p[100005]; // 底数
    int a[100005]; //指数
    for (int i = 2;i * i <= n;i++)
    {
        if (n % i == 0)
        {
            p[cnt] = i;
            while (n % i == 0)
            {
                n /= i;
                a[cnt]++;
            }
            cnt++;
        }
        if (n > 1)
        {
            p[cnt] = n;
            a[cnt] = 1;
            cnt++;
        }
    }
    /*** p存储底数
         a存储指数
         cnt为因数个数 - 1
    */
    

    2.因数个数和因数和

    // 需先分解质因数
    int c = 1,s = 1;// c为个数,s为因数之和
    for (int i = 0;i < cnt;i++)
    {
        c *= a[i] + 1;
        int t = 1;
        for (int j = 0 ;j <= a[i];j++)
        {
            c += t;
            t *= p[i];
        }
        s *= t;
    }
    
    

    3.最大公因数

    (1)直接调用gcd函数

    gcd = __gcd(a,b);

    (2)

    int gcd (int a,int b)
    {
        if (b == 0)  return a;
        return (b,a % b);
    }
    

    4.埃氏筛法

    bool vis[1000005];// vis[i] == 1是质数,否则不是质数
    bool prime()
    {
        for (int i = 1;i <= 1000000;i++)  vis[i] = 1;
        vis[0] = vis[1] = 0;
        for (int i = 2;i <= 1000000;i++)
        {
            if (vis[i] == 1)
            {
                for (int j = i * 2;j <= 1000000;j+=i)
                {
                    vis[j] = 0;
                }
            }
        }
    }
    

    5.质因子分解

    唯一分解定理:给定一个大于1的正整数n,一定可以写成:n = p1^a1 * p2^a2 * ……pn*ai;

    p1,p2……pn都是质数。

    int n;
    cin >> n;
    for (int i = 2;i * i <= n;i++)
    {
        while(n % i == 0)
        {  
            cout << i << " ";
            n /= i;
        }
    }
    if (n != 1)
        cout << n;
    
    
  • 通过的题目

  • 最近活动

    This person is lazy and didn't join any contests or homework.
  • 最近编写的题解

    This person is lazy and didn't write any solutions.

题目标签

客观题
1