A number is Almost-K-Prime if it has exactly K prime numbers (not necessarily distinct) in its prime factorization. For example, 12 = 2 * 2 * 3 is an Almost-3-Prime and 32 = 2 * 2 * 2 * 2 * 2 is an Almost-5-Prime number. A number X is called Almost-K-First-P-Prime if it satisfies the following criterions:
For example, if K=3 and P=2, the numbers 18 = 2 * 3 * 3 and 12 = 2 * 2 * 3 satisfy the above criterions. And 630 = 2 * 3 * 3 * 5 * 7 is an example of Almost-5-First-4-Pime.
For a given K and P, your task is to calculate the summation of Φ(X) for all integers X such that X is an Almost-K-First-P-Prime.
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each case starts with a line containing two integers K (1 ≤ K ≤ 500) and P (1 ≤ P ≤ K).
For each case, print the case number and the result modulo 1000000007.
3
3 2
5 4
99 45
Case 1: 10
Case 2: 816
Case 3: 49939643
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include<string.h> 7 #include 8 #include 9 #include 10 using namespace std; 11 typedef long long LL; 12 typedef unsigned long long ll; 13 bool prime[5000]= {0}; 14 int su[600]; 15 LL dp[600][600]; 16 LL ola[600]; 17 LL ola1[600]; 18 const LL mod=1e9+7; 19 LL quick(int n,int m); 20 int main(void) 21 { 22 int i,j,k,p,q; 23 for(i=2; i<=100; i++) 24 { 25 for(j=i; i*j<=5000; j++) 26 { 27 prime[i*j]=true; 28 } 29 } 30 int ans=1; 31 for(i=2; i<=5000; i++) 32 { 33 if(!prime[i]) 34 { 35 su[ans++]=i; 36 } 37 } 38 memset(dp,0,sizeof(dp)); 39 dp[0][0]=1; 40 dp[1][1]=2; 41 for(i=1; i<=500; i++) 42 { 43 for(j=i; j<=500; j++) 44 { 45 dp[i][j]=(((dp[i][j-1]+dp[i-1][j-1])%mod)*(su[i]))%mod; 46 } 47 } 48 ola[1]=su[1]; 49 ola1[1]=su[1]-1; 50 for(i=2; i<=500; i++) 51 { 52 ola[i]=(su[i]*ola[i-1])%mod; 53 ola1[i]=(su[i]-1)*ola1[i-1]%mod; 54 } 55 for(i=1; i<=500; i++) 56 { 57 ola[i]=quick(ola[i],mod-2); 58 } 59 scanf("%d",&k); 60 int s; 61 for(s=1; s<=k; s++) 62 { 63 scanf("%d %d",&p,&q); 64 LL cnt=dp[q][p]; 65 LL cns=ola[q]; 66 LL bns=ola1[q]; 67 LL sum=((cnt*cns)%mod*bns)%mod; 68 printf("Case %d: ",s); 69 printf("%lld\n",sum); 70 } 71 return 0; 72 } 73 LL quick(int n,int m) 74 { 75 LL ans=1; 76 LL N=n; 77 while(m) 78 { 79 if(m&1) 80 { 81 ans=(ans*N)%mod; 82 } 83 N=(N*N)%mod; 84 m/=2; 85 } 86 return ans; 87 }
1298 - One Theorem, One Year
京公网安备 11010802041100号