codeforces|codeforces #305 547C C. Mike and Foam(莫比乌斯反演)
题目链接：
点击打开链接
题目大意：
给出一列数，最开始集合 为空，然后q次操作，每次给出一个x，如果第x个数存在，那么删去，不存在添加，问操作完互质的数有多少对
题目分析：
问互质的数的对数，裸裸的数论题
首先f(k)定义为gcd(ai,aj)(1<=i
定义cnt[i]为集合中是i的倍数的数有多少个
那么F(k) = C(2 , cnt[k] ) 结论很显然
所以我们可以利用莫比乌斯反演，在每次根据要添加或删除的数修正结果，然后输出即可
也就是对给出的数分解质因数，然后因为如果当前数含有某个质因数的2次方及以上，u等于0
而且因为2*3........*17 > 500000，所以质因数的个数不会超过6个，只要枚举2^6种影响到的F(k)即可
总的复杂度q*2^6，绝对的秒出
【codeforces|codeforces #305 547C C. Mike and Foam(莫比乌斯反演)】
#include
#include
#include
#include
#include
#define MAX 500007using namespace std;
typedef long long LL;
int n,q,x;
int a[MAX];
int u[MAX];
int used[MAX];
int cnt[MAX];
int maxPrime[MAX];
vector v;
LL ans;
void init ( )
{
memset ( maxPrime , -1 , sizeof ( maxPrime ) );
for ( int i = 1 ;
i < MAX ;
i++ ) u[i] = 1;
for ( int i = 2 ;
i < MAX ;
i++ )
{
if ( ~maxPrime[i] ) continue;
for ( int j = 1 , t = i ;
t < MAX ;
j++,t += i )
{
maxPrime[t] = i;
u[t] = j%i==0?0:-u[t];
}
}
}void update ( int x , int f )
{
v.clear();
while ( x > 1 )
{
int p = maxPrime[x];
v.push_back(p);
while ( x%p == 0 )
x /= p;
}
int m = v.size();
int total = 1< 推荐阅读
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- Codeforces580|Codeforces580 D. Kefa and Dishes（状压dp）
- Codeforces22|Codeforces22 D. Segments（贪心）
- codeforces|codeforces 667C C. Reberland Linguistics(dp)
- Codeforces|Codeforces Round #263 Div.1 B Appleman and Tree --树形DP【转】