UVA 12716 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 를 따라 뒤 척 이 며 제거 하 겠 습 니 다. 그것들 을 한 배열 에 넣 고 계산 하면 미리 처리 하면 된다.
다 친 후에 또 하나의 폭력 적 인 절 차 를 밟 아 답 을 달 렸 는데 결 과 는 모두 옳 았 다. 그러나 시간 을 초과 했다. 처음에 예비 처 리 를 모두 롱 롱 롱 형 으로 부 여 했 기 때문에 뒤 척 일 때% 연산 이 있어 서 느 릴 수 있 기 때문에 int 로 바 꾸 면 맞다.

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

#define IN freopen("c:\\Users\
it\\desktop\\input.txt", "r", stdin)    
#define OUT freopen("c:\\Users\
it\\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\
it\\desktop\\input.txt", "r", stdin)    
//#define OUT freopen("c:\\Users\
it\\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