## Friday, December 11, 2015

### HDU 4135-Co-prime - Inclusion–exclusion principle

http://www.cnblogs.com/UniqueColor/p/4733546.html
Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N. Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

Input
The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 1015) and (1 <=N <= 109).

Output
For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

http://www.acmerblog.com/hdu-4135-co-prime-7138.html
 `03` `typedef` `long` `long` `LL;`
 `04` `LL a,b;`
 `05` `int` `n;`
 `06` `LL tol,ans;`
 `07` `void` `dfs(``int` `s,LL mul,``int` `t)`
 `08` `{`
 `09` `    ``if``(s==cnt){`
 `10` `        ``if``(t) ans=ans+tol/mul;`
 `11` `        ``else` `ans=ans-tol/mul;`
 `12` `        ``return``;`
 `13` `    ``}`
 `14` `    ``dfs(s+1,mul,t);`
 `15` `    ``dfs(s+1,mul*f[s],1-t);`
 `16` `}`
 `17` `LL cal(LL x)`
 `18` `{`
 `19` `    ``if``(x==0) ``return` `0;`
 `20` `    ``tol=x;`
 `21` `    ``ans=0;`
 `22` `    ``dfs(0,1,1);`
 `23` `    ``return` `ans;`
 `24` `}`
 `25` `int` `main()`
 `26` `{`
 `27` `  ``// freopen("1.in","r",stdin);`
 `28` `    ``int` `T,ca=0;`
 `29` `    ``scanf``(``"%d"``,&T);`
 `30` `    ``while``(T--){`
 `31` `        ``scanf``(``"%I64d%I64d%d"``,&a,&b,&n);`
 `32` `        ``if``(n==1) { ``printf``(``"Case #%d: %I64d\n"``,++ca,b-a+1);``continue``;}`
 `33` `        ``cnt=0;`
 `34` `        ``for``(``int` `j=2;j*j<=n;j++){`
 `35` `            ``if``(n%j==0){`
 `36` `                ``f[cnt++]=j;`
 `37` `                ``while``(n%j==0) n/=j;`
 `38` `            ``}`
 `39` `        ``}`
 `40` `        ``if``(n>1) f[cnt++]=n;`
 `41`
 `42` `       ``// for(int i=0;i
 `43` `        ``printf``(``"Case #%d: %I64d\n"``,++ca,cal(b)-cal(a-1));`
 `44` `    ``}`
 `45` `}`
Inclusion–exclusion principle
https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
In combinatorics (combinatorial mathematics), the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
$|A \cup B| = |A| + |B| - |A \cap B|,$
where A and B are two finite sets and |S| indicates the cardinality of a set S (which may be considered as the number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The double-counted elements are those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection.
The principle is more clearly seen in the case of three sets, which for the sets AB and C is given by
$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$
Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of n sets:
1. Include the cardinalities of the sets.
2. Exclude the cardinalities of the pairwise intersections.
3. Include the cardinalities of the triple-wise intersections.
4. Exclude the cardinalities of the quadruple-wise intersections.
5. Include the cardinalities of the quintuple-wise intersections.
6. Continue, until the cardinality of the n-tuple-wise intersection is included (if n is odd) or excluded (n even).