test/miller-rabin.test.cpp

• View this file on GitHub
• Last update: 2023-01-09 22:14:04+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://algo-method.com/submissions/760056

Depends on

• miller-rabin (素数判定法) (src/math/miller-rabin.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../src/math/miller-rabin.hpp"

#include <iostream>

int main() {
	// int n; std::cin >> n;
	// for (int _ = 0 ; _ < n ; _++) {
	// 	long long a; std::cin >> a;
	// 	std::cout << (zawa::isprime(a) ? "Yes" : "No") << std::endl;
	// }
	std::cout << "Hello World" << std::endl;
}

/* 
 * アルゴ式 ミラー-ラビンの素数判定法
 * https://algo-method.com/submissions/760056
 */

#line 1 "test/miller-rabin.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "src/math/miller-rabin.hpp"

#include <vector>

namespace zawa::impl {

long long modpow(__int128_t a, __int128_t b, long long mod) {
	long long res = 1LL;
	a %= mod;
	while (b) {
		if (b & 1) {
			res = ((__int128_t)res * a) % mod;
		}
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}

std::vector<long long> cond = { 2, 325, 9375, 28178, 450775, 978504, 1795265022 };

} // namespace zawa::impl

namespace zawa {

bool isprime(long long n) {
	if (n <= 1) {
		return false;
	}
	if (n == 2 or n == 3) {
		return true;
	}
	if (!(n & 1)) {
		return false;
	}
	long long s = 0LL, d = n - 1;
	while (d % 2 == 0) {
		s++;
		d >>= 1;
	}
	for (auto c : impl::cond) {
		if (c % n == 0) {
			return true;
		}
		long long x = impl::modpow(c, d, n);
		if (x != 1) {
			long long t = 0;
			for ( ; t < s ; t++) {
				if (x == n - 1) {
					break;
				}
				x = ((__int128_t)x * x) % n;
			}
			if (t == s) {
				return false;
			}
		}
	}
	return true;
}

} // namespace zawa
#line 4 "test/miller-rabin.test.cpp"

#include <iostream>

int main() {
	// int n; std::cin >> n;
	// for (int _ = 0 ; _ < n ; _++) {
	// 	long long a; std::cin >> a;
	// 	std::cout << (zawa::isprime(a) ? "Yes" : "No") << std::endl;
	// }
	std::cout << "Hello World" << std::endl;
}

/* 
 * アルゴ式 ミラー-ラビンの素数判定法
 * https://algo-method.com/submissions/760056
 */

Back to top page