Co-prime
Problem's Link:
推荐:
Mean:
给你一个区间[l,r]和一个数n，求[l,r]中有多少个数与n互素。
analyse:
经典的容斥原理题。
如果题目是说求1~n中有多少个数与n互质，我们一定反应应该是欧拉函数。
但是如果n特别大或者说是求某个给定区间与n互素的个数，这时用欧拉函数就行不通。
容斥做法：首先我们可以在O(sqrt(n))内求出n的所有质因数p1,p2,p3....pk。
对于每个质因数pi，1~r中不与它互素的个数就是r/pi。
然后就是如何容斥了？
首先我们来分析，n<=1e9，那么n的质因数的个数最多不超过9个，那么我们就可以对n的所有质因数进行组合来计算。
例如：30的质因数有3个(2,3,5),我们可以用二进制来表示所有的情况：
001： 5
010： 3
011： 3 5
100： 2
101： 2 5
110： 2 3
111： 2 3 5
假设有k个质因数，那么只需用2^k-1个数的二进制来表示即可。
剩下的就是容斥了，设cnt为1的个数(选中的质因数的个数)，当cnt为奇数，sum加上此次的;cnt为偶数，sum减去此次的。
具体看代码。
Time complexity: O(N)
Source code:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-08-10-19.49 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std; LL solve( LL r , LL n) { vector < LL > ve; LL up =( LL) sqrt(n); for( LL i = 2; i <= up; ++ i) { if(n % i == 0) { ve . push_back( i); while(n % i == 0) n /= i; } } if(n > 1) ve . push_back(n); LL sum = 0 , si = ve . size(); up =( 1 << si) - 1; for( LL i = 1; i <= up; ++ i) { LL tmp = i , bits = 0 , mul = 1 , cnt = 0; while( tmp) { if( tmp & 1) { mul *= ve [ bits ]; ++ cnt; } ++ bits; tmp = tmp >> 1; } LL cur = r / mul; if( cnt & 1) sum += cur; else sum -= cur; } return sum; } int main() { ios_base :: sync_with_stdio( false); cin . tie( 0); LL t , cas = 1; cin >> t; while( t --) { LL l , r ,n; cin >> l >> r >>n; if( l > r) swap( l , r); printf( "Case #%lld: %lld \n " , cas ++ , r - l + 1 -( solve( r ,n) - solve( l - 1 ,n))); } return 0; } /* */