首页 / 软件开发 / 数据结构与算法 / 算法题：CodeForces 236B - Easy Number Challenge（数论：求因子个数）

算法题：CodeForces 236B - Easy Number Challenge（数论：求因子个数）2014-03-17 csdn博客 shuangde800链接：

http://www.codeforces.com/problemset/problem/236/B

题目：

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 （230）.

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 （230）.

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