AOJ1076:Time Manipulation

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1076
[1,n]の整数のうちa_k(1 <= k <= m)の倍数を除いたものを1個拾ったときの期待値を求める

方針

包除原理。m<=20なので2^m通りの選び方についてビット数をカウントして係数の正負を決めればよい。
計算するものは選んだ数の公倍数の和とその個数。
公倍数の個数は n / lcm, 公倍数の和はlcm * (n / lcm) * ((n/lcm)+1)。

nが大きいのでlong longで計算することに注意。

以下ソースコード

#include <iostream>
#include <cstdio>

using namespace std;

#define ll long long

ll sum(ll arg){
	return arg * (arg+1) / 2;
}

ll gcd(ll a, ll b){
	if(b == 0) return a;
	return gcd(b, a%b);
}

ll lcm(ll a, ll b){
	return a * b / gcd(a,b);
}

int main(){
	int n,m;
	
	while(cin>>n>>m){
		ll a[m];
		double ret = 0;
		long long s = sum(n);
		long long allnum = n;
		
		if((n|m) == 0) break;
		for(int i=0;i<m;i++) cin >> a[i];
		
		//包除原理
		for(ll i=1;i < (1 << m); i++){
			int bitnum = 0;
			ll lc=1;
			for(int j=0;j<m;j++){
				if(i&(1<<j)){ //j番目要素が含まれている
					bitnum++;
					lc = lcm(lc, a[j]);
				}
			}
			if(bitnum%2 == 1){
				s -= lc * sum(n / lc);
				allnum -= n / lc;
			}else{
				s += lc * sum(n / lc);
				allnum += n / lc;
			}
		}
		if(allnum == 0){
			ret = 0;
		}else{
			ret = (double)s / allnum;
		}
		printf("%.7f\n",ret);
	}
}