计蒜客 小游戏 容斥原理（Java版）

蒜头君和花椰菜君在玩一个游戏。蒜头君先手，他选择一个非空集合，集合中的元素都是整数对 ( a , b ) (a, b) (a,b)，满足条件： 1 &lt; = a &lt; b &lt; = N 1 &lt;= a &lt; b &lt;= N 1<=a<b<=N，且 g c d ( a , b ) = 1 gcd(a, b) = 1 gcd(a,b)=1。比如 N = 5 N=5 N=5，可以选择集合 { ( 1 , 2 ) , ( 3 , 4 ) , ( 3 , 5 ) (1, 2), (3, 4), (3, 5) (1,2),(3,4),(3,5)}。

花椰菜君后手，他需要找到一个整数 x ∈ { 2 , 3 , ⋯ &ThinSpace; , N } x in { 2,3,cdots,N} x∈{ 2,3,⋯,N}，使得对于任意整数对 ( a , b ) (a, b) (a,b)，满足以下两个条件的任意一个： a , b &lt; x a, b&lt;x a,b<x； a , b ≥ x a,bgeq x a,b≥x。例如集合 { ( 1 , 2 ) , ( 3 , 4 ) } {(1, 2), (3, 4)} { (1,2),(3,4)}， x x x 可以等于 3 3 3。如果花椰菜君找不到这样的 x x x，则蒜头君获胜。现在蒜头君想知道，有多少种不同的方案能使他获胜。

输入格式

输入一行，输入一个整数 N N N（ 2 ≤ N ≤ 20 2 leq N leq 20 2≤N≤20）。

输出格式

输出一行，输出一个整数，表示蒜头君可以选择的集合个数，结果可能会很大，输出对 1 0 9 10^9 109 取余的结果即可。

这题卡了我好久，还是看的老师的代码才能ac。 AC代码：

import java.util.Scanner;
//先预处理出来能选择的整数对为m对，那么总的集合数为2^m，我们以x为基础容斥，首先枚举一个x，
//减去满足一个x的方案数，然后加上满足两个x的方案数，再减去满足3个x的。。
public class Main {
	static int mod=(int) 1e9;
	static int MAXN=22,MAX=500;
	static int gcd(int a,int b){
		return b>0?gcd(b,a%b):a;
	}
	static int tot[][]=new int[MAXN][MAXN];//存储区间[a,b]的互质数的对数
	static int p2[]=new int[MAX];
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int res=0;
		p2[0]=1;
		for(int i=1;i<MAX;i++)
			p2[i]=p2[i-1]*2%mod;
		for(int a=1;a<n;++a){//预处理对于每个区间[a,b]中有多少对互质数
			for(int b=a+1;b<=n;b++){
				for(int i=a;i<=b;i++){
					for(int j=i+1;j<=b;j++){
						if(gcd(i,j)==1)
							tot[a][b]++;
					}
				}
			}
		}
		for(int mask=0;mask<(1<<(n-1));++mask){
			long prev=1,curr=1,sum=0;
			for(int x=1;x<n;x++){//这一次选的这些划分成若干区间
				if((mask&(1<<(x-1)))!=0){
					sum++;
					curr=curr*p2[tot[(int) prev][x]]%mod;//在这一段区间有多少对可选的，就有2的多少次方种可选的集合
					prev=x+1;
				}
			}
			curr=curr*p2[tot[(int) prev][n]]%mod;
			res+=(sum%2==0?curr:-curr);
			res%=mod;
		}
		res+=mod;
		res%=mod;
		System.out.println(res);
		sc.close();
	}
}