首页 > itarticle > lcm (分解定理求约数的个数)

lcm (分解定理求约数的个数)

admin 1月 18, 2021 0

传送门：Codeforces Round 518 (Div. 2) B.LCM
Description

Ivan has number b. He is sorting through the numbers aa from 1 to 10^18, and for every aa writes [a,b]/a on blackboard. Here [a,b] stands for least common multiple of aa and bb. Ivan is very lazy, that’s why this task bored him soon. But he is interested in how many different numbers he would write on the board if he would finish the task. Help him to find the quantity of different numbers he would write on the board.

Input

The only line contains one integer — b (1≤b≤10^10).

Output

Print one number — answer for the problem.

Sample Input

1

Sample Output

1

Sample Input

2

Sample Output

2

Thinking
给出一个数字b，然后求[a,b]/a，的不同取值有多少种，[a,b]值最小公倍数。这里有(a*b)/gcd(a,b) == [a,b]。原式转化为b/gcd(a,b)。当分母gcd(a,b)>b的时候，取值唯一变成0，实际上也永远不可能大于b。因此答案就变成了求b的约数的个数。可以线性遍历求出约数个数，复杂度为O(sqrt(b))。但这里利用唯一分解定理。
Code

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 


int index = 0;
bool isprime[100010];
int prime[100010];

void ()
{
    for (int i = 2;i <= 100000; ++i){
       isprime[i] = true;
  }
    for (int i = 2;i*i <= 100000; ++i){
     if (isprime[i]){
            for (int j = i*i;j <= 100000; j += i){
              isprime[j] = false;
         }
        }
    }
    for (int i = 2;i <= 100000; ++i){
       if (isprime[i]){
            prime[index++] = i;
      }
    }
}
int main ()
{
    get_prime();
 long long total;
   int ans = 1;
    scanf ("%lld",&total);

    for (int i = 0;i < index; ++i){
     if (prime[i] > total){
           break;
      }
        int num = 0;
        if (total % prime[i] == 0){
         while (total%prime[i] == 0){
                ++num;
               total /= prime[i];
           }
            ans *= (num + 1);
        }
    }
    if (total > 1){
      ans *= 2;
    }
    printf ("%dn",ans);
    return 0;
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能