本文共 2011 字，大约阅读时间需要 6 分钟。

链接：

题目：

B. Easy Number Challenge

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's denote d(n) as the number of divisors of a positive integer n. You are given three integers a, b and c. Your task is to calculate the following sum:

Find the sum modulo 1073741824 (2³⁰).

Input

The first line contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 100).

Output

Print a single integer — the required sum modulo 1073741824 (2³⁰).

Sample test(s)

input

2 2 2

output

20

input

5 6 7

output

1520

Note

For the first example.

• d(1·1·1) = d(1) = 1;
• d(1·1·2) = d(2) = 2;
• d(1·2·1) = d(2) = 2;
• d(1·2·2) = d(4) = 3;
• d(2·1·1) = d(2) = 2;
• d(2·1·2) = d(4) = 3;
• d(2·2·1) = d(4) = 3;
• d(2·2·2) = d(8) = 4.

So the result is 1 + 2 + 2 + 3 + 2 + 3 + 3 + 4 = 20.

分析与总结：

裸的求因子个数，数据比较水可以暴力过，但是只要给个100 100 100， 就会因TLE被别人hack掉的。

对于我这种数学弱逼，打CF时只能临时百度个更高效的的方法了...

条件：给定任意一个一个正整数N

要求：求其因子的个数

首先给出结论：对于任意的整型N，分解质因数得到N= P1^x1 * P2^x2* …… * Pn^xn;

则N的因子个数M为 M=（x1+1） * （x2+1） * …… *（xn+1）;

首先 举个例子吧

24 = 2^3 * 3^1；

其质因子有：为2和3  指数为 3和1

那么对于2 有0 1 2 3四种指数选择，对于3 有0 1两种指数选择

所以 就是4 * 2 = 8 个因子个数

如果还是不懂，那么我们就列举出来吧

2 3

2^0*3^0=1             2^0*3^1=3

2^1*3^0=2             2^1*3^1=6

2^2*3^0=4             2^2*3^1=12

2^3*3^0=8             2^3*3^1=24

结果很清晰了吧？？其实这里用到了数学的排列组合的知识

也就是说每一个质因子的不同指数幂与其它质因子相乘，得到的结果一定不会重复

因此能够将所有的因子都列举出来。

所以N的因子数M，我们可以用M=（x1+1） * （x2+1） * …… *（xn+1）表示

参考资料：

代码：

#include
   
    #include
    
     #include
     
      using namespace std;const int MOD = 1073741824;const int Maxn = 1000005;int w[6600];int ans[Maxn], n;// 判断是否是质数bool isPrime(int n) {    if(n<=1)return false;    if(n==2)return true;    if(n!=2&&n%2==0)return false;    int i;    for(i=3;i*i<=n;i+=2)        if(n%i==0)return false;    return true;}// 计算因子个数int count(int n){    if(ans[n]!=-1)return ans[n];    int a=n, i=0, sum=1;    while(a!=1 && i
      
        MOD) sum %= MOD;       }       printf("%d\n",sum);   }   return 0;}
      
     
    
   

—— 生命的意义，在于赋予它意义。   
     
       
       
      
       
    原创 ， By D_Double (转载请标明)