題目鏈接 Problem Description There is a set including all positive integers that are not more then n. HazelFan wants to choose some integers from this set ...
Problem Description There is a set including all positive integers that are not more then n. HazelFan wants to choose some integers from this set, satisfying: 1. The number of integers chosen is at least 1 and at most k. 2. The product of integers chosen is 'free from square', which means it is divisible by no square number other than 1. Now please tell him how many ways are there to choose integers, module 10^9+7.
Input The first line contains a positive integer T(1≤T≤5), denoting the number of test cases.
For each test case:
A single line contains two positive integers n,k(1≤n,k≤500).
Output For each test case:
A single line contains a nonnegative integer, denoting the answer.
Sample Input 2 4 2 6 4
Sample Output 6 19
題意：從1~n中任意取1~K個數（同一個數不能用多次），這些數的乘積不能被任意一個數的平方整除（除了 1 ），求有多少種取法？
思路：可以從以上題意分析出，取的多個數不能有相同的質數因數。由於n<=500，所以一個數小於sqrt(n)的質數因數可能有多個，但大於sqrt(n)的質數因數只可能有一個。而小於sqrt(n)的質數有2 、3、5、7、11、13、17、19，一共8個，所以對這8個質數因數進行狀壓。然後就是背包DP，因為成績不能含有 質數因數的平方，所以需要進行分組，將含有相同大於sqrt（n）的數放在一組，保證這樣的數只能每次取一個，也就是分組背包。
代碼如下：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <vector> using namespace std; const int mod=1e9+7; const int N=505; int dp[N][256]; int r[N],st[N]; int p[8]={2,3,5,7,11,13,17,19}; vector<int>v[N]; int main() { int T; cin>>T; while(T--) { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<N;i++) { v[i].clear(); r[i]=i; st[i]=0; } memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<8;j++) { if(i%p[j]==0 && i%(p[j]*p[j])!=0) st[i]|=1<<j,r[i]/=p[j]; else if(i%(p[j]*p[j])==0){ st[i]=-1; break; } } } for(int i=1;i<=n;i++) { if(st[i]==-1) continue; if(r[i]==1) v[i].push_back(i); else v[r[i]].push_back(i); } // for(int i=1;i<=n;i++) // { // for(int j=0;j<v[i].size();j++) // cout<<v[i][j]<<" "; // cout<<endl; // } for(int i=1;i<=n;i++) { if(st[i]==-1 || v[i].size()==0) continue; for(int j=m-1;j>=0;j--) { for(int s=0;s<256;s++) { for(int k=0;k<v[i].size();k++) { int d=st[v[i][k]]; if((s&d)!=0) continue; dp[j+1][s|d]=(dp[j+1][s|d]+dp[j][s])%mod; } } } } int ans=0; for(int i=1;i<=m;i++) { for(int j=0;j<256;j++) ans=(ans+dp[i][j])%mod; } printf("%d\n",ans); } return 0; }
