數學分析 + 容斥原理 - URAL 1907 Coffee and Buns 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;