competitive-programming/codeforces/rounds/364-easy-number-challenge.cpp at main · UnknownHacker1/competitive-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
 * Easy Number Challenge  [236B]
 * Problem:  https://codeforces.com/problemset/problem/236/B
 * Verdict:  ACCEPTED        Solved: 2021-04-02
 * Language: C++17 (GCC 7-32)
 * Runtime:  342 ms     Memory: 7800 KB
 * Tags:     implementation, number theory
 * Author:   BidoTeima
 * Source:   https://codeforces.com/contest/236/submission/111787838
 */

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
ll MOD = (1 << 30);
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int a, b, c;
	ll sum = 0;
	cin >> a >> b >> c;
	vector<ll> dp((int)1e6+2, -1);
	for (ll i = 1; i <= a; i++) {
		for (ll j = 1; j <= b; j++) {
			for (ll k = 1; k <= c; k++) {
				ll prod = i * j * k;
				if (dp[prod] != -1) {
					sum = (sum + dp[prod])%MOD;
					continue;
				}
				ll ret = 0;
				for (ll x = 1; x * x <= prod; x++) {
					if (prod % x == 0) {
						if ((prod / x) == x)ret += 1;
						else ret += 2;
					}
				}
				dp[prod] = ret;
				sum = (sum + dp[prod]) % MOD;
			}
		}
	}
	cout << sum;
	return 0;
}