글 읽기 - 도저히 모르겠습니다... 오버플로우 방지 방법에 대해 알려주실 분 계신가요?

dmswl022329 2년 전 0

문제의 입력에서 a, X0, c 의 범위가 10^18 까지 인데

a 와 X0 이 둘다 10^18 - 1 이 나오고

mod 가 10^18 이면

첫 연산부터 10^36 을 계산하게 되어 오버플로우가 납니다.

그래서 첫번째 해결방법이 모듈러 연산의 값을 음수로 내리는 것 이었습니다.

위에서 가정한 mod a X0 를 가지고 다음과 같이 연산을 하면

(((a % mod) - mod) * ((X0 % mod) - mod) + mod) % mod

a%mod 는 a 이고

a - mod 는 -1 입니다

X0%mod 도 마찬가지로 X0

X0 - mod = -1

-1 * -1 = 1

(1 + mod) % mod = 1

이렇게 했습니다.

하지만 이러면 음수 상태에서 곱해서 오버플로우가 날 수 있기 때문에

모듈러 연산할 수의 절대값의 제곱근 값이 root(10^18) 보다 작게 해서 곱하면 될거라고 생각했습니다.

그럼에도 4%에서 틀렸습니다 가 나옵니다.

수 범위를 어떻게 하면 오버플로우를 방지하면서 계산할 수 있을까요?

방법을 제시해 주세요...

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll mod, a, c, X0, n, g;
ll pow2[65];
ll powa[65];


// N 을 10^18 의 제곱근값인 10^9 보다 작게 만들어 반환한다
ll root(ll N){
	if(N <= 1000000000){
		return N % mod;
	}else{
		return (N % mod) - mod;
	}
}

void pow_2(){
	pow2[0] = 1;
	for(int i = 1; i < 65; i++) pow2[i] = pow2[i-1] * 2;
}

void pow_a(){
	powa[0] = a % mod;
	for(int i = 1; i < 65; i++) powa[i] = (root(powa[i-1]) * root(powa[i-1]) + mod) % mod;
}

ll npow(ll N){
	if(a == 0) return 0;
	ll res = 1;
	vector<int> v;
	for(int i = 62; i >= 0; i--) {
		if(N >= pow2[i]){
			v.push_back(i);
			// cout << pow2[i] << "\n";
			N -= pow2[i];
		}
	}
	for(int i = 0; i < v.size(); i++){
		ll tem1, tem2;
		tem1 = res % mod;
		tem2 = powa[v[i]] % mod;
		tem1 = root(tem1);
		tem2 = root(tem2);
		res = (tem1 * tem2 + mod) % mod;
		// res = (((res % mod) - mod) * ((powa[v[i]] % mod) - mod) + mod) % mod;
	}
	// for(int i = 0; i < v.size(); i++) cout << v[i] << "\n";
	return res;
}

ll sol(ll low, ll high, ll size){
	if(size == 1) return 1;
	if(size % 2 == 0){
		ll tem1, tem2;
		tem1 = sol(low, high/2, size/2) % mod;
		tem2 = (npow(size / 2) + 1) % mod;
		tem1 = root(tem1);
		tem2 = root(tem2);
		return (tem1 * tem2 + mod) % mod;
		// return (((sol(low, high/2, size/2) % mod) - mod) * (((npow(size / 2) + 1) % mod) - mod) + mod) % mod;
	}else{
		ll tem1, tem2;
		tem1 = npow(high) % mod;
		tem2 = sol(low, high - 1, size - 1) % mod;
		tem1 = root(tem1);
		tem2 = root(tem2);
		return (tem1 + tem2 + mod) % mod;
		// return (((npow(high) % mod) - mod) + ((sol(low, high - 1, size - 1) % mod) - mod) + mod) % mod;
	}
}
int main() {
	ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
	cin >> mod >> a >> c >> X0 >> n >> g;
	pow_2();
	pow_a();
	// cout << pow2[62];
	// for(int i = n; i >= 1; i--) cout << (((npow(i) % mod) * (X0 % mod) + (c % mod) * (sol(0, i-1, i) % mod)) % mod) << "\n";
	// ll p = ((npow(n) % mod) - mod) * ((X0 % mod) - mod) + ((c % mod) - mod) * ((sol(0, n-1, n) % mod) - mod) + mod) % mod;
	ll p = (root(npow(n)) * root(X0) + root(c) * root(sol(0, n-1, n)) + mod) % mod;
	// cout << p << "\n";
	cout << p % g;
	// cout << mod << " " << g << "\n";
	//	cout << (((npow(n) % mod) * (X0 % mod) + (c % mod) * (sol(0, n-1, n) % mod)) % mod) % g	
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.