Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory
の中で の倍数で無い数の を求める．包除原理を用いて， の倍数である数の個数，和をそれぞれ求めて引いて計算するようにした．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <bitset>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
ll n , m ;
ll c ;
ll lcm ( ll m , ll n ) {
if ( m == 0 || n == 0 ) return 0 ;
return (( m / __gcd ( m , n )) * n );
}
ll f ( vector < ll > v ) {
int k = v . size ();
c = 0 ;
ll ret = 0 ;
rep ( i , 1 << k ) {
ll x = 1 ;
int cnt = 0 ;
bool ch = false ;
rep ( j , k ) {
if ( i & ( 1 << j )) {
x = lcm ( x , v [ j ]);
cnt ++ ;
}
if ( x > n ) {
ch = true ;
break ;
}
}
if ( x == 1LL ) continue ;
if ( ch ) continue ;
ll o = n / x , s ;
if ( o % 2 == 0 ) {
s = ( o / 2 ) * ( 2 * x + ( o - 1 ) * x );
} else {
s = o * ( x + ( o - 1 ) * x / 2 );
}
if ( cnt % 2 == 0 ) {
ret -= s ;
c -= o ;
} else {
ret += s ;
c += o ;
}
}
return ret ;
}
int main () {
while ( cin >> n >> m ) {
if ( n == 0 && m == 0 ) break ;
bool flag = false ;
vector < ll > v ( m );
rep ( i , m ) {
cin >> v [ i ];
if ( v [ i ] == 1 ) {
flag = true ;
}
}
if ( flag ) {
cout << fixed ;
cout . precision ( 20 );
cout << 0.0 << endl ;
continue ;
}
ll sum = n * ( n + 1 ) / 2 ;
ll ret = f ( v );
ll res = sum - ret ;
double cnt = n - c ;
cout << fixed ;
cout . precision ( 20 );
cout << res / cnt << endl ;
}
return 0 ;
}