UVA12716 GCD XOR 數論數學構造

題目給你一個N，讓你求 兩個數字 A,B,且 A>=B<=N,是的 gcd(A,B) == A^B

N的范圍是 3*10^7大的嚇人一開始沒敢想構造，因為就算構造開的數組也太大了，已經10^7了，後來想了半天在^運算這裡也沒有想出來什麼，所以沒辦法還是大膽構造吧，構造就去按照他題目的意思來了，構造兩個數字 i,j其中j是i的倍數，那麼j + i與i的最大公約數肯定是i了，那麼(j+i)^i == i這樣構造出來的就算滿足了，然後再模仿gcd輾轉相除的願意 把它們放在一個數組裡計數，這樣預處理即可

打好以後又打了一個暴力程序來跑答案，結果都是對的，但是交了超時，因為一開始預處理都給賦值了 long long型，在輾轉相除的時候 有個%運算，會導致很慢，所以改成int就對了

#define  _CRT_SECURE_NO_WARNINGS
/*#include
#include
#include
#include
#include
#include
using namespace std;

#define IN freopen("c:\\Users\\nit\\desktop\\input.txt", "r", stdin)    
#define OUT freopen("c:\\Users\\nit\\desktop\\output.txt", "w", stdout)   


int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
int main()
{
	OUT;
	int ans[510],k=0;
	memset(ans,0,sizeof(ans));
	for(int i=1;i<500;i++)
	{
		for(int b=1;b<=i;b++)
		{
			for(int a=b;a<=i;a++)
			{
				if((a^b)==gcd(a,b))
					ans[i]++;
			}
		}
		printf("%d\t",ans[i]);
		if(k%10==0)puts("");
		k++;
	}
	return 0;
}*/

#include
#include
#include
#include
#include
#include
using namespace std;

//#define IN freopen("c:\\Users\\nit\\desktop\\input.txt", "r", stdin)    
//#define OUT freopen("c:\\Users\\nit\\desktop\\outpu1t.txt", "w", stdout)   

#define ll long long

#define MAXN 30000000 + 5

ll ans[MAXN];

void init() {
	for(ll i = 1;i 0 && y > 0;) {
					int tmp = x%y;
					x = y;
					y = tmp;
					if((x + y) == i)
						ans[i + j]++;
				}
			}
		}
	}
	for(int i = 2;i