Codeforces 235E. Number Challenge DP DP

dp(a,b,c,p) = sigma ( dp(a/p^i,b/p^j,c/p^k) * ( 1+i+j+k) )
【Codeforces 235E. Number Challenge DP】表示用小于等于p的素数去分解的结果有多少个

E. Number Challenge time limit per test 3 seconds memory limit per test 512 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?≤?2000).
Output Print a single integer — the required sum modulo 1073741824 (230).
Sample test(s) input

2 2 2

output

20

input

4 4 4

output

328

input

10 10 10

output

11536

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.

import java.util.*; public class CF235E { class Triple {Triple(){}Triple(int _x,int _y,int _z) { this.x=_x; this.y=_y; this.z=_z; this.sort(); }public int x,y,z; void sort() { if(this.z(); } long gao(int deep,Triple tri) {if(deep==pn) return 1; if(map[deep].get(tri)!=null) return (long) map[deep].get(tri); long ret=0; int p=primes[deep]; for(int x=tri.x,i=0; x!=0; x/=p,i++) { for(int y=tri.y,j=0; y!=0; y/=p,j++) { for(int z=tri.z,k=0; z!=0; z/=p,k++) { ret+=gao(deep+1,new Triple(x,y,z))*(i+j+k+1)%mod; if(ret>=mod) { ret-=mod; } } } } map[deep].put(tri, ret); return ret; } CF235E(){ init(); Scanner in = new Scanner(System.in); a=in.nextInt(); b=in.nextInt(); c=in.nextInt(); System.out.println(gao(0,new Triple((int)a,(int)b,(int)c))); } public static void main(String[] args) { new CF235E(); } }