B. Easy Number Challenge
time limit per test2 seconds
memory limit per test256 megabytes
题目链接:传送门
Let's denote d(n) as the number of divisors of a positive integern. 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 integersa, b andc (1?≤?a,?b,?c?≤?100).
Output Print a single integer — the required sum modulo1073741824 (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.
意解:暴力,先把暴力枚举一边,记录每个数出现的个数,然后Nsqrt(N)找因子;
AC代码:
#include
#include
#include
#include
#define For(i,a,n) for(int i = a;
i <= n;
i++)using namespace std;
const int M = 1e6;
const int INF = 1LL << 30;
int ma[M + 10];
int main()
{
int a,b,c;
int ans = 0;
scanf("%d %d %d",&a,&b,&c);
For(i,1,a)
For(j,1,b)
For(k,1,c)
ma[i * j * k]++;
for(int i = 1;
i <= M;
i++)
{
if(ma[i])
for(int p = 1;
p * p <= i;
p++)
{
if(i % p == 0)
{
ans += ma[i];
if(p * p != i) ans += ma[i];
}
}
}
cout< 【B. Easy Number Challenge】
