| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 1562 | Accepted: 478 |
Description
Input
Output
Sample Input
4 2 3 4 5 4 2 4 6 8 7 2 3 4 5 7 6 8
Sample Output
1 0 34题目翻译：给出n(n<10000)个数，这些数<=10000，要求选出四个数字且他们的最大公约数为1的（注意：不需要两两互质），有多少种选法。
解题思路：本题可以先计算n个数字选四个总共有多少种选法，然后减去公约数不是1的。把共同具有某一素因子的数字划分到同一个集合，属于统一集合的四个数最大公约数一定大于1，如果四个数字不同时属于任何集合则最大公约数一定为1。用总的组合数减去那些四个数字同时被同一个集合包括了的组合数，所得结果即为最终答案。但是这些一个四个数字的组合可能同时属于若干个集合，因此需要在这些集合之间进行容斥原理，以求每个需要被减去的四个数字的组合都恰好被减掉一次。
首先，先将算法流程说一下，原理后面会有
Step 1：预处理，求组合数C（n，4），存于数组p中，方便下面运算！
Step 2：组合素数，用prime数组记录由m(m<=5)个素数相乘所得数的素因子
Step 3：读入当前数为a，将a分解为质因数形式，注意每个质因数只被记录一次
例如： 182=2*7*13 ———> m=3 so，相加
2=2 ——>m=1 so，相加
91=7*13 ——>m=2 so，相减
注意12=2^2*3等这种是B=p1^k1*p2^k2+...这种有质因数指数不为一的合数记录不同因子的个数
12=2*2*3 则 12会被分为2*3，多余的2被消去了，因此m=2；
Step 4：将分出的素数进行组合，并统计每种的方案数
例如：12=2^2*3——>12=2*3——>cnt[2]++,cnt[3]++,cnt[6]++
Step 5：处理之后，ans赋值为0
Step 6：for i 2-->10000
if （m==奇数） ans:=ans+C(cnt[i],4)
else ans:=and-C(cnt[i],4);
Step 7：输出ans
原理：首先考虑一个问题，1000以内6,7,8,9的倍数有多少个？答案是
1000div6+1000div7+1000div8+1000div9
-1000div(6*7)-1000div(6*8)-1000div(6*9)-1000div(7*8)-1000div(7*9)-1000div(8*9)
+1000div(6*7*8)+1000div(6*8*9)+1000div(7*8*9)
-1000div(6*7*8*9)
这是容斥原理的一个最简单的应用，类比这道题，Step3到4其实将每个数a的不重复约数记录了下来，
有公共约数的四个数的方案要从ans中减去，多减的要加上
显然m为奇时要减，m为偶时要加，这和”1000以内6,7,8,9的倍数有多少个？“这个问题奇偶是反的，
由于a最大为10000，所以m最大可以有5 (2*3*5*7*11<10000,2*3*5*7*11*13>10000)
此表格解释利用2进制查找素因子组合
| 1 | 2 | 4 | |
| 1 | T | ||
| 2 | T | ||
| 3 | T | T | |
| 4 | T | ||
| 5 | T | T | |
| 6 | T | T | |
| 7 | T | T | T |
#include<iostream>
#include<stdio.h>
#include<string.h>
#define MAX 10005
using namespace std;
int cnt[MAX],num[MAX],prime[5];//数组不必过大，5个单位即可
long long p[MAX]={0}; //必须用大整数
void Solve(int n){
int i,j,tol=0,k,sum;
for(i=2;i*i<=n;i++){ //计算素因子个数
if(n%i==0)
prime[tol++]=i;
while(n%i==0)//去重复因子
n/=i;
}
if(n!=1) prime[tol++]=n; //如果本身就是大于n开方的素数，需要加一，这点不要忘记
for(i=1;i<(1<<tol);i++){ //总共有1~2^tol-1个组合
k=1,sum=0;
for(j=0;j<tol;j++)//巧妙利用二进制来查找到所有素因子组合构成的数
if(i&(1<<j)){
k*=prime[j];
sum++;
}
cnt[k]++; //记录含有因子K的数的个数,比如n=30,则cnt[2]++,cnt[3]++,cnt[5]++;
//cnt[6]++,cnt[10]++,cnt[15]++;cnt[30]++;
num[k]=sum;//记录k中含有素因子的个数 num[2]=1,num[3]=1,num[5]=1,num[6]=2,
} //num[10]=2,num[15]=2,num[30]=3,
}
int main(){
int m,n;
long long i;
for(i=4;i<MAX;i++) //先打表，提高效率，i<4时p[i]为0；
p[i]=i*(i-1)*(i-2)*(i-3)/24;
while(~scanf("%d",&n)){
memset(cnt,0,sizeof(cnt));
for(i=0;i<n;i++){
scanf("%d",&m);
Solve(m); //求解其素因子，并统计相关数据
}
long long ans=0;
for(i=0;i<MAX;i++)
if(cnt[i]>=4)//剪枝，必须大于等于四
if(num[i]&1) //假如含有素因子个数为奇数，则加上；否则减去
ans+=p[cnt[i]];
else
ans-=p[cnt[i]];
cout<<p[n]-ans<<endl; //最后用总的减去不符合的四元组个数
}return 0;
}
