#P5276. Skyfall

    ID: 4314 传统题 1000ms 233MiB 尝试: 130 已通过: 35 难度: 9 上传者: 标签>CF2800省选/NOI-交换求和顺序莫比乌斯反演线性筛倍数枚举最小公倍数欧几里得算法三元环计数按度数定向By

Skyfall

题目描述

设 d(n)d(n) 表示正整数 nn 的约数个数。

给定三个正整数 a,b,ca,b,c,计算:

$\displaystyle \sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c} d(ijk)$

答案对 1073741824=2301073741824=2^{30} 取模。

输入格式

一行三个整数 a,b,ca,b,c。

1≤a,b,c≤20001\le a,b,c\le 2000。

输出格式

输出一个整数,表示

$\displaystyle \sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c} d(ijk)$

对 10737418241073741824 取模后的结果。

样例 #1

2 2 2
20

样例 #2

4 4 4
328

样例 #3

10 10 10
11536

样例说明

对于第一个样例:

  • d(1×1×1)=d(1)=1d(1\times1\times1)=d(1)=1;
  • d(1×1×2)=d(2)=2d(1\times1\times2)=d(2)=2;
  • d(1×2×1)=d(2)=2d(1\times2\times1)=d(2)=2;
  • d(1×2×2)=d(4)=3d(1\times2\times2)=d(4)=3;
  • d(2×1×1)=d(2)=2d(2\times1\times1)=d(2)=2;
  • d(2×1×2)=d(4)=3d(2\times1\times2)=d(4)=3;
  • d(2×2×1)=d(4)=3d(2\times2\times1)=d(4)=3;
  • d(2×2×2)=d(8)=4d(2\times2\times2)=d(8)=4。

因此答案为:

1+2+2+3+2+3+3+4=201+2+2+3+2+3+3+4=20。