锐客网

  1. 首页 > it技术 > >

数学|Codeforces 236B Easy Number Challenge 【因子和】

数学codeforces

题目链接：Codeforces 236B Easy Number Challenge
B. Easy Number Challenge
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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.
So the result is 1?+?2?+?2?+?3?+?2?+?3?+?3?+?4?=?20.
预处理因子和就可以了。
【数学|Codeforces 236B Easy Number Challenge 【因子和】】AC代码：

#include #include #include #include #include #include #include #include #define CLR(a, b) memset(a, (b), sizeof(a)) using namespace std; typedef long long LL; typedef pair pii; const int MAXN = 1e6 + 1; const int MOD = 1073741824; const int INF = 0x3f3f3f3f; void add(LL &x, LL y) { x += y; x %= MOD; } int sum[MAXN]; void getsum() { for(int i = 1; i < MAXN; i++) { if(i == 1) sum[i] = 1; else sum[i] = 2; } for(int i = 2; i * i < MAXN; i++) { for(int j = i; j * i < MAXN; j++) { if(i != j) { sum[i*j] += 2; } else { sum[i*j] += 1; } } } } int main() { getsum(); int a, b, c; while(scanf("%d%d%d", &a, &b, &c) != EOF) { LL ans = 0; for(int i = 1; i <= a; i++) { for(int j = 1; j <= b; j++) { for(int k = 1; k <= c; k++) { add(ans, sum[i*j*k]); } } } printf("%lld\n", ans); } return 0; }

    推荐阅读


    上一篇：SPOJ DISUBSTR - Distinct Substrings or SUBST1 - New Distinct Substrings 【不同子串数目】

    下一篇：《2.3|《2.3 系统主界面的制作》