• 质数和约数

  ---

  试除法判定质数

  问题描述

  给定 n 个正整数 ai，判定每个数是否是质数。

  输入格式

  第一行包含整数 n。

  接下来 n 行，每行包含一个正整数 ai。

  输出格式

  共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。

  数据范围

  1≤n≤100,1≤a_i≤2³¹−1

  输入样例

  2
  2
  6
  1
  2
  3

  输出样例

  Yes
  No
  1
  2

  问题分析

  质数定义：一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数，这个数就是质数。

  给定一个数 x,判断 x 是否为质数：

  用 x 除以 2 ~ x - 1 中的每个数，如果出现了余数为 0,则这个数不是质数，如果没有出现余数为 0,则这个数是质数。

  优化：

  一个数 x 分解成两个数的乘积，则这两个数中，一定有一个数大于根号 x，一个数小于根号x。

  所以，可以用 x 除以 2 ~ 根号x 中的每个数，如果出现了余数为 0,则这个数不是质数，如果没有出现余数为 0,则这个数是质数。

  代码

  #include
  using namespace std;
  const int N=110;
  int n;
  int a[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=1;i<=n;i++)
      {
          cin>>a[i];
          if(is_prime(a[i])) cout<<"Yes"<

  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

  分解质因数

  问题描述

  给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

  输入格式
  第一行包含整数 n。

  接下来 n 行，每行包含一个正整数 ai。

  输出格式
  对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

  每个正整数的质因数全部输出完毕后，输出一个空行。

  数据范围
  1≤n≤100,2≤ai≤2×10⁹

  输入样例

  2
  6
  8
  1
  2
  3

  输出样例

  2 1
  3 1
  
  2 3
  
  1
  2
  3
  4
  5

  问题分析

  • x 的质因子最多只包含一个大于 根号x 的质数。如果有两个，这两个因子的乘积就会大于 x，矛盾。

  • i 从 2 遍历到 根号x。 用 x / i，如果余数为 0，则 i 是一个质因子。

  • s 表示质因子 i 的指数，x /= i 为 0，则 s++， x = x / i 。

  • 最后检查是否有大于 根号x 的质因子，如果有，输出。

  代码

  #include
  using namespace std;
  int n;
  void div(int n)
  {
      for(int i=2;i<=n/i;i++)
      {
          if(n%i==0)
          {
              int s=0;
              while(n%i==0) n/=i,s++;
              cout<1) cout<>n;
      int x;
      for(int i=1;i<=n;i++)
      {
          cin>>x;
          div(x);
          cout<

  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

  筛质数

  问题描述

  给定一个正整数 n，请你求出 1∼n 中质数的个数。

  输入格式

  共一行，包含整数 n。

  输出格式

  共一行，包含一个整数，表示 1∼n 中质数的个数。

  数据范围

  1≤n≤106

  输入样例

  8
  1

  输出样例

  4
  1

  问题分析

  代码

  朴素筛法

  #include
  using namespace std;
  const int N=1000010;
  int prime[N],cnt;
  bool st[N];
  int n;
  void get_prime(int n)
  {
      for(int i=2;i<=n;i++)
      {
          if(st[i]) continue;
          prime[cnt++]=i;
          for(int j=i+i;j<=n;j+=i)
              st[j]=true;
      }
  }
  int main()
  {
      cin>>n;
      get_prime(n);
      cout<

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23

线性筛法

#include
using namespace std;
const int N=1000010;
int prime[N],cnt;
bool st[N];
int 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;
        }
    }
}
int main()
{
    cin>>n;
    get_prime(n);
    cout<

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25

试除法求约数

问题描述

给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai。

输出格式

输出共 n 行，其中第 i 行输出第 i 个整数 ai 的所有约数。

数据范围

1≤n≤100,1≤ai≤2×10⁹

输入样例

2
6
8
1
2
3

输出样例

1 2 3 6 
1 2 4 8 
1
2

问题分析

什么是约数：如果一个数a除以另一个数b的余数为0，即 a%b == 0, 则b是a的约数。

如何求一个数x的所有约数：

用 x 除以 1 到 x 的所有数，如果余数是0，则把除数加到答案中。

优化

• 如果 a / b = c···0，则一定有 a % c = b····0。所以一个数 x 的约数肯定是成对存在的，对称轴是 根号x。
• 因此，只需要用 x 除以 1 到 根号x 之间的数，如果余数是0，则把除数以及x / 除数加到答案中。

代码

#include
using namespace std;

vector get_divisors(int x)
{
    vector res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / 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 x : res) cout << x << ' ';
        cout << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

约数个数

问题描述

给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 10⁹+7 取模。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai。

输出格式

输出一个整数，表示所给正整数的乘积的约数个数，答案需对 10⁹+7 取模。

数据范围

1≤n≤100,1≤ai≤2×10⁹

输入样例

3
2
6
8
1
2
3
4

输出样例

12
1

问题分析

一个数的约数是由这个数的几个质因子相乘得到的。

例如：12 的质因子有 2，3。12的约数有：1，2，3，4，6，12。

约数1 是由 0 个 2， 0 个3相乘得到的。
约数2 是由 1 个 2， 0 个3相乘得到的。
约数3 是由 0 个 2， 1 个3相乘得到的。
约数4 是由 2 个 2， 0 个3相乘得到的。
约数6 是由 1 个 2， 1 个3相乘得到的。
约数12 是由 2 个 2， 1 个3相乘得到的。
12 可以分解为：2^2*31。所以2可以取 0 ~ 2个，3种取法。3可以取 0~1 个，2种取法。12的约数一共：2 * 3 = 6个。

也就是：把一个数N 写成：N = (p1^x1)(p^x2)(p3x3)…(pk^xk)，其中pi为质数。则N的约数个数为：(x1+1)(x2+1)(x3+1)…(xk+1)

代码

#include
using namespace std;
typedef long long ll;
const int N=110,MOD=1e9+7;
int main()
{
    int n;
    cin>>n;
    unordered_map primes;
    while(n--)
    {
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++)
            while(x%i==0)
            {
                primes[i]++;
                x/=i;
            }
        if(x>1) primes[x]++;
    }
    ll res=1;
    for(auto x:primes) res=res*(x.second+1)%MOD;
    cout<

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26

约数之和

问题描述

给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 10⁹+7 取模。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 10⁹+7取模。

数据范围

1≤n≤100,1≤ai≤2×109

输入样例

3
2
6
8
1
2
3
4

输出样例

252
1

问题分析

如果 N=p1^c1∗p2^c2∗…∗pk^ck

约数个数：(c1+1)∗(c2+1)∗…∗(ck+1)

约数之和： (p1⁰+p1¹+…+p1^c1)∗…∗(pk⁰+pk¹+…+pk^ck)

while (b - - ) t = (t * a + 1) % mod;

t=t∗p+1

t=1
t=p+1
t=p²+p+1
…
t=p^b+p^b-1+…+1

代码

#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int main()
{
    int n;
    cin>>n;
    unordered_map 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)
    {
        int a=p.first,b=p.second;
        ll t=1;
        while(b--) t=(t*a+1)%mod;
        res=res*t%mod;
    }
    cout<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

最大公约数

问题描述

给定 n 对正整数 ai,bi，请你求出每对数的最大公约数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数对 ai,bi。

输出格式

输出共 n 行，每行输出一个整数对的最大公约数。

数据范围

1≤n≤105,1≤ai,bi≤2×10⁹

输入样例

2
3 6
4 6
1
2
3

输出样例

3
2
1
2

问题分析

什么是最大公约数
最大公约数（Greatest Common Divisor）指两个或多个整数共有约数中最大的一个。也称最大公因数、最大公因子，a， b的最大公约数记为（a，b），同样的，a，b，c的最大 公约数记为（a，b，c），多个 整数的最大公约数也有同样的记号。求最大公约数有多种 方法，常见的有 质因数分解法、 短除法、 辗转相除法、 更相减损法。

辗转相减法求最大公约数
用(a，b)表示a和b的最大公因数：有结论(a，b)=(a，ka+b)，其中a、b、k都为自然数。

也就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数，其公约数不变，比如(4，6)=(4+6，6)=(4，6+2×4)=2.

要证明这个原理很容易：如果p是a和ka+b的公约数，p整除a，也能整除ka+b.那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的.

基于上面的原理，就能实现我们的迭代相减法：(78，14)=(64，14)=(50，14)=(36，14)=(22，14)=(8，14)=(8，6)=(2，6)=(2，4)=(2，2)=(0，2)=2

基本上思路就是大数减去小数，一直减到能算出来为止，在作为练习的时候，往往进行到某一步就已经可以看出得值.

辗转相减到辗转相除
迭代相减法简单，不过步数比较多，实际上我们可以看到，在上面的过程中，由(78，14)到(8，14)完全可以一步到位，因为(78，14)=(14×5+8，14)=(8，14)，由此就诞生出我们的辗转相除法.

即：(a， b) = (a % b， b) = （b, a %b）

相当于每一步都把数字进行缩小，等式右边就是每一步对应的缩小结果。

对（a， b）连续使用辗转相除，直到小括号内右边数字为0，小括号内左边的数就是两数最大公约数。

代码

#include
using namespace std;
int n;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    cin>>n;
    for(int i=0;i>a>>b;
        cout<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18