Coffee and Buns
Problem's Link: http://www.bnuoj.com/v3/contest_show.php?cid=6415#problem/H
Mean:
给定两个数a和n，求[1,n]中有多少个x满足：gcd(4*(a+x),a^2+x^2)>1。
analyse:
gcd(4(a+x),a^2+x^2)>1 ----> gcd(a+x,(a+x)^2-2ax)>1 ----> gcd(a+x,2ax)>1 (gcd(a,b)=gcd(b,a%b)
假设a是偶数，那么gcd(a+x,2ax)>1 ----> gcd(a+x,ax)
设最大公约数为g，则g|ax，g|a+x
如果g|a，那么g|x，如果g|x，那么g|a，所以只要x是a任意一个因子的倍数就合法
假设a是奇数，那么有2种情况
1.x是奇数
2.x是a任意一个因子的倍数
所以要求1~maxn中与a，gcd > 1 的个数，就是求1~maxn与某一个num不互素的个数，要用到容斥原理。
Time complexity: O(N)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-03-15.46
* 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;
const LL MAXN = 10 +( LL) 1e6;
LL a ,n , ans , cnt;
LL p [ MAXN ];
LL rongchi( LL n)
{
LL rup =( 1 << cnt ), su , tmp , ans = 0;
for( LL i = 1; i < rup; ++ i)
{
su = 0 , tmp = 1;
for( LL j = 0; j < cnt; ++ j)
{
if(( 1 << j) & i)
{
tmp *=p [ j ];
su ++;
}
}
if( su & 1) ans +=n / tmp;
else ans -=n / tmp;
}
return ans;
}
LL solve( LL a , LL n)
{
cnt = 0;
LL up = int( sqrt( a) + 1e-5);
for( LL i = 2; i <= up; ++ i)
{
if( !( a % i))
{
while( !( a % i)) { a /= i; }
p [ cnt ++ ] = i;
}
}
if( a > 1) p [ cnt ++ ] = a;
return rongchi(n);
}
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
while( cin >> a >>n)
{
if( a & 1) cout <<((n + 1) / 2 + solve( a ,(n / 2))) << endl;
else cout << solve( a ,n) << endl;
}
return 0;
}
/*
*/
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-03-15.46
* 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;
const LL MAXN = 10 +( LL) 1e6;
LL a ,n , ans , cnt;
LL p [ MAXN ];
LL rongchi( LL n)
{
LL rup =( 1 << cnt ), su , tmp , ans = 0;
for( LL i = 1; i < rup; ++ i)
{
su = 0 , tmp = 1;
for( LL j = 0; j < cnt; ++ j)
{
if(( 1 << j) & i)
{
tmp *=p [ j ];
su ++;
}
}
if( su & 1) ans +=n / tmp;
else ans -=n / tmp;
}
return ans;
}
LL solve( LL a , LL n)
{
cnt = 0;
LL up = int( sqrt( a) + 1e-5);
for( LL i = 2; i <= up; ++ i)
{
if( !( a % i))
{
while( !( a % i)) { a /= i; }
p [ cnt ++ ] = i;
}
}
if( a > 1) p [ cnt ++ ] = a;
return rongchi(n);
}
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
while( cin >> a >>n)
{
if( a & 1) cout <<((n + 1) / 2 + solve( a ,(n / 2))) << endl;
else cout << solve( a ,n) << endl;
}
return 0;
}
/*
*/
