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;
}
/*

*/