CF236 B. Easy Number Challenge【求约数个数】 cf

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).
Examples 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.

【CF236 B. Easy Number Challenge【求约数个数】】 So the result is 1?+?2?+?2?+?3?+?2?+?3?+?3?+?4?=?20.
代码如下

#include const int MOD=1073741824; const int MAX=1e6; int a[MAX+10]; int pp()//判断一个数约数的个数 {a[1]=1; for(int i=2; i<=MAX; i++) {int q=i; a[i]=1; for(int j=2; j*j<=q; j++)//提高效率 if(q%j==0) {int s=1; while(q%j==0) s++,q/=j; a[i]*=s; } if(q>1)//当它的约数中有素数时 a[i]*=2; } } int main() { pp(); int x,b,c,i,j,k; long long sum; while(~scanf("%d%d%d",&x,&b,&c)) { sum=0; for(i=1; i<=x; i++) for(j=1; j<=b; j++) for(k=1; k<=c; k++) sum=(sum+a[i*j*k]%MOD)%MOD; printf("%I64d\n",sum); } }