1159: One Theorem, One Year
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 21 Solved: 12
[Submit][Status][Web Board]Description
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:
1. X is an Almost-K-Prime and
2. X has all and only the first P (P ≤ K) primes in its prime factorization.
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
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).
Output
For each case, print the case number and the result modulo
1000000007 .
Sample Input
3 3 2 5 4 99 45
Sample Output
Case 1: 10 Case 2: 816 Case 3: 49939643
求出素數后然后，然后然后就是排列組合的問題了。
dp[i][j]表示在前i個素數里選j個數相乘的和
dp[i][j]= dp[i-1][j-k]*exp[i][k] 0<=k<=j求和
這里邊算邊模
a[i][j]表示在前i個素數里j個數組成結果，則
a[i][j]=mul[i]*dp[i][j-1]
這里也邊算模。
#include<stdio.h>
#include<string.h>
#include<math.h>
int pri[550],b[3705]; //這里之前是3500要錯哦
long long dp[505][505],a[505][505];
long long mod=1000000007;
int GetPri()
{
int i,j,tot;
memset(b,0,sizeof(b));
i=2;
tot=0; //寫了那么素數篩法了，居然會在這里載?。。。?br /> while (i<=3700)
{
while (b[i]) i++;
pri[++tot]=i;
j=i;
while (j<=3700)
{
b[j]=1;
j+=i;
}
}
return 0;
}
int Cal()
{
int i,j;
long long sum,mul;
dp[0][0]=1;
for (i=1; i<=500 ; i++ )
{
dp[i][0]=1;
sum=0;
for (j=1; j<=500 ; j++ )
{
sum=(sum*pri[i]+dp[i-1][j-1]*pri[i]) % mod; //哎，方程的優化，還是沒有經驗啊??！這里之前我是寫了個三重的循環呢。可以迭代的啊。
dp[i][j]=(dp[i-1][j]+sum) % mod;
}
}
mul=1;
for (i=1; i<=500 ; i++ )
{
mul=mul*(pri[i]-1) % mod; //方程優化！??！
for (j=i; j<=500 ; j++ )
a[i][j]=mul*dp[i][j-i] % mod;
}
}
int main()
{
int p,cas,n,m;
GetPri();
Cal();
scanf("%d",&p);
cas=0;
while (p--)
{
scanf("%d%d",&n,&m);
printf("Case %d: %lld\n",++cas,a[m][n]);
}
return 0;
}
總結：方程的優化，降低維數！?。。。。。。。。。。。。。。。。。?！
真的是弱爆了啊。。。。。。。。