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.
题目大意：
就是求 小于等于 a*b*c的因子个数之和。。。
解体思路：
素因子分解，然后将每一个素因子的个数记在一个数组中，然后循环。。。
因子数 等于 素因子个数的指数+1 的连乘。。。
上代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e5+5;
const int mod = 1073741824;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
LL gcd(LL a, LL b)
{
if(b == 0)
return a;
return gcd(b, a%b);
}
bool prime[maxn];
int p[maxn/10];
int k;
void isprime()
{
k=0;
LL i,j;
memset(prime, true, sizeof(prime));
for(i=2; i<maxn; i++)
{
if(prime[i])
{
p[k++]=i;
for(j=i*i; j<maxn; j+=i)
{
prime[j]=false;
}
}
}
}
int num[1000];
int fac[maxn];
int cnt;
void fenjie(int m)
{
memset(num, 0, sizeof(num));
cnt=0;
for(int i=0; p[i]*p[i]<=m&&i<k; i++)
{
if(m%p[i]==0)
{
fac[cnt]=p[i];
while(m%p[i]==0)
{
num[cnt]++;
m/=p[i];
}
cnt++;
}
}
if(m>1)
{
fac[cnt]=m;
num[cnt++]=1;
}
}
int main()
{
isprime();
int a, b, c;
while(cin>>a>>b>>c)
{
int ret = 0;
for(int i=1; i<=a; i++)
{
for(int j=1; j<=b; j++)
{
for(int k=1; k<=c; k++)
{
int sum = 1;
if(i*j*k == 1)
ret++;
else
{
fenjie(i*j*k);
for(int i=0; i<cnt; i++)
sum *= (num[i]+1);
ret += sum;
if(ret > mod)
ret %= mod;
}
}
}
}
cout<<ret%mod<<endl;
}
return 0;
}
