#248998 (Python3) No.8039 April Fool Tekitou

提出ソース
結果

問題	No.8039 April Fool Tekitou
ユーザー	しらっ亭
提出日時	2018-04-01 23:52:08
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	31 ms / 2,000 ms
コード長	9,174 bytes
コンパイル時間	141 ms
コンパイル使用メモリ	12,544 KB
実行使用メモリ	10,368 KB
最終ジャッジ日時	2024-06-26 06:15:19
合計ジャッジ時間	562 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	31 ms 10,368 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
print(20170387916)

'''

// sniplate: headers
// {{{ template
// clang-format off
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <array>
#include <unordered_map>
#include <complex>
#include <deque>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>
#include <tuple>
#include <cstring>
using namespace std;

#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(n))
#define sz(x) ((int)(x).size())
#define TEN(n) ((ll)(1e##n))
#define fst first
#define snd second

string DBG_DLM(int &i){return(i++==0?"":", ");}
#define DBG_B(exp){int i=0;os<<"{";{exp;}os<<"}";return os;}
template<class T>ostream&operator<<(ostream&os,vector<T>v);
template<class T>ostream&operator<<(ostream&os,set<T>v);
template<class T>ostream&operator<<(ostream&os,queue<T>q);
template<class T>ostream&operator<<(ostream&os,priority_queue<T>q);
template<class T,class K>ostream&operator<<(ostream&os,pair<T,K>p);
template<class T,class K>ostream&operator<<(ostream&os,map<T,K>mp);
template<class T,class K>ostream&operator<<(ostream&os,unordered_map<T,K>mp);
template<int I,class TPL>void DBG(ostream&os,TPL t){}
template<int I,class TPL,class H,class...Ts>void DBG(ostream&os,TPL t){os<<(I==0?"":", ")<<get<I>(t);DBG<I+1,TPL,Ts...>(os,t);}
template<class T,class K>void DBG(ostream&os,pair<T,K>p,string delim){os<<"("<<p.first<<delim<<p.second<<")";}
template<class...Ts>ostream&operator<<(ostream&os,tuple<Ts...>t){os<<"(";DBG<0,tuple<Ts...>,Ts...>(os,t);os<<")";return os;}
template<class T,class K>ostream&operator<<(ostream&os,pair<T,K>p){DBG(os,p,", ");return os;}
template<class T>ostream&operator<<(ostream&os,vector<T>v){DBG_B(forr(t,v){os<<DBG_DLM(i)<<t;});}
template<class T>ostream&operator<<(ostream&os,set<T>s){DBG_B(forr(t,s){os<<DBG_DLM(i)<<t;});}
template<class T>ostream&operator<<(ostream&os,queue<T>q){DBG_B(for(;q.size();q.pop()){os<<DBG_DLM(i)<<q.front();});}
template<class T>ostream&operator<<(ostream&os,priority_queue<T>q){DBG_B(for(;q.size();q.pop()){os<<DBG_DLM(i)<<q.top();});}
template<class T,class K>ostream&operator<<(ostream&os,map<T,K>m){DBG_B(forr(p,m){os<<DBG_DLM(i);DBG(os,p,"->");});}
template<class T,class K>ostream&operator<<(ostream&os,unordered_map<T,K>m){DBG_B(forr(p,m){os<<DBG_DLM(i);DBG(os,p,"->");});}
#define DBG_OVERLOAD(_1,_2,_3,_4,_5,_6,macro_name,...)macro_name
#define DBG_LINE(){char s[99];sprintf(s,"line:%3d | ",__LINE__);cerr<<s;}
#define DBG_OUTPUT(v){cerr<<(#v)<<"="<<(v);}
#define DBG1(v,...){DBG_OUTPUT(v);}
#define DBG2(v,...){DBG_OUTPUT(v);cerr<<", ";DBG1(__VA_ARGS__);}
#define DBG3(v,...){DBG_OUTPUT(v);cerr<<", ";DBG2(__VA_ARGS__);}
#define DBG4(v,...){DBG_OUTPUT(v);cerr<<", ";DBG3(__VA_ARGS__);}
#define DBG5(v,...){DBG_OUTPUT(v);cerr<<", ";DBG4(__VA_ARGS__);}
#define DBG6(v,...){DBG_OUTPUT(v);cerr<<", ";DBG5(__VA_ARGS__);}
#define DEBUG0(){DBG_LINE();cerr<<endl;}
#ifdef LOCAL
#define out(...){DBG_LINE();DBG_OVERLOAD(__VA_ARGS__,DBG6,DBG5,DBG4,DBG3,DBG2,DBG1)(__VA_ARGS__);cerr<<endl;}
#else
#define out(...)
#endif

using ll=long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pil=pair<int,ll>;using pli=pair<ll,int>;
using vs=vector<string>;using vvs=vector<vs>;using vvvs=vector<vvs>;
using vb=vector<bool>;using vvb=vector<vb>;using vvvb=vector<vvb>;
using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;
using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;
using vd=vector<double>;using vvd=vector<vd>;using vvvd=vector<vvd>;
using vpii=vector<pii>;using vvpii=vector<vpii>;using vvvpii=vector<vvpii>;
template<class A,class B>bool amax(A&a,const B&b){return b>a?a=b,1:0;}
template<class A,class B>bool amin(A&a,const B&b){return b<a?a=b,1:0;}
ll ri(){ll l;cin>>l;return l;} string rs(){string s;cin>>s;return s;}
// clang-format on
// }}}

vi D = {
	24,24,4,16,80,12,32,16,24,12,96,8,32,4,96,2,48,16,4,80,24,16,16,8,48,32,8,2,48,8,16,16,12,4,48,8,60,24,8,8,48,4,8,16,16,4,64,8,12,32,8,2,160,4,96,12,12,4,64,6,8,16,16,24,72,4,8,16,10,16,32,16,12,16,8,4,64,32,16,32,48,8,12,2,192,4,8,8,48,16,4,24,16,8,32,6,24,32,16,4
};

// sniplate: is_probable_prime
/// n <= 2^20(10^6) 以下では試し割りの方が早い
template <class BinOp> bool is_prime_impl(const uint64_t &n, const uint64_t *witness, BinOp modmul) {
	if (n == 2) return true;
	if (n < 2 || n % 2 == 0) return false;
	const int64_t m = n - 1, d = m / (m & -m);
	auto modpow = [&](int64_t a, int64_t b) {
		int64_t res = 1;
		for (; b; b /= 2) {
			if (b & 1) res = modmul(res, a);
			a = modmul(a, a);
		}
		return res;
	};
	auto suspect = [&](uint64_t a, uint64_t t) {
		a = modpow(a, t);
		while (t != n - 1 && a != 1 && a != n - 1) {
			a = modmul(a, a);
			t = modmul(t, 2);
		}
		return a == n - 1 || t % 2 == 1;
	};
	for (const uint64_t *w = witness; *w; w++) {
		if (*w % n != 0 && !suspect(*w, d)) return false;
	}
	return true;
}
bool is_probable_prime(const uint64_t &n) {
	assert(n < (1ULL << 63));
	if (n < (1ULL << 32)) {
		/// n < 2^32
		constexpr uint64_t witness[] = {2, 7, 61, 0};
		auto modmul = [&](uint64_t a, uint64_t b) -> uint64_t { return a * b % n; };
		return is_prime_impl(n, witness, modmul);
	}
	else {
		/// n < 2^63
		constexpr uint64_t witness[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022, 0};
		/// if u128 is available
		auto modmul = [&](uint64_t a, uint64_t b) -> uint64_t { return (uint64_t)((__uint128_t)a * b % n); };
		// otherwise
		// auto modmul = [&](uint64_t a, uint64_t b) {
		//   uint64_t res = 0;
		//   for (; b; b /= 2) {
		//     if (b & 1) res = (res + a) % n;
		//     a = (a + a) % n;
		//   }
		//   return res;
		// };
		return is_prime_impl(n, witness, modmul);
	}
}

// sniplate: sieve
/// O(n log log n)
/// [2, n)
vector<bool> sieve(int n) {
	vector<bool> flg(n, 1);
	for (int i = 0; i < 2; i++) {
		flg[i] = false;
	}
	for (int j = 4; j < n; j += 2) {
		flg[j] = false;
	}
	int lim = int(sqrt(n)) + 1;
	for (int i = 3; i < lim; i += 2) {
		if (flg[i]) {
			for (int j = i * i; j < n; j += i * 2) {
				flg[j] = 0;
			}
		}
	}
	return flg;
}

// sniplate: primes
/// O(n log log n)
/// [2, n)
vector<int> primes(int n) {
	vector<int> ret;
	if (n <= 2) return ret;
	ret.emplace_back(2);

	vector<bool> flg = sieve(n);

	for (int i = 3; i < n; i += 2) {
		if (flg[i]) ret.emplace_back(i);
	}
	return ret;
}

// sniplate: number_of_divisors
/// primes に pow(x, 1.0/3) 以下の素数の一覧を入れておくこと
/// isPrime は x 以下に対応できるものを使うこと(sqrt3(x)以下ではない)
/// O(sqrt3(x))
int number_of_divisors(int64_t x, const vector<int> &primes) {
	int ret = 1;

	for (int64_t p : primes) {
		if (p * p * p > x) break;
		int count = 1;
		while (x % p == 0) {
			x /= p;
			count++;
		}
		ret *= count;
	}

	if (is_probable_prime(x)) ret *= 2;
	else {
		int rx = sqrt(x);
		if (rx * rx == x && is_probable_prime(rx)) {
			ret *= 3;
		}
		else if (x != 1) {
			ret *= 4;
		}
	}
	return ret;
}

// sniplate: template
void Main() {
	out(D);	
/*
i=36, D[i]=60
i=68, D[i]=10
*/

	rep(i, 100) out(i, D[i]);

	map<int, int> M;
	rep(i, 100) M[D[i]]++;
	out(M);

	auto P4 = primes(pow(3e10/16, 1.0/4)+1);
	auto P3 = primes(pow(3e10/32, 1.0/3)+1);
	auto P2 = primes(pow(3e10/64, 1.0/2)+1);
	int s4 = sz(P4);
	int s3 = sz(P3);
	int s2 = sz(P2);
	out(P3);

	auto P1 = primes(3e10/144+1);
	int s1 = sz(P1);
	out(s1,s2,s3,s4);

	auto Q = primes(pow(3e10, 1.0/3)+1);

	constexpr ll LIM = 30000000000LL;

	auto check36 = [&](ll z) {
		if (number_of_divisors(z - 36 + 68, Q) != 10) return false;
		if (number_of_divisors(z - 36 + 52, Q) != 160) return false;
		if (number_of_divisors(z - 36 + 84, Q) != 192) return false;
		if (number_of_divisors(z - 36 + 19, Q) != 80) return false;
		if (number_of_divisors(z - 36 +  4, Q) != 80) return false;

		rep(a, 100) {
			if (number_of_divisors(z-36+a, Q) != D[a]) {
				return false;
			}
		}
		return true;
	};

	rep(i, s4) {
		ll p4 = P4[i];
		rep(j, s2) {
			ll p2 = P2[j];
			if (p2 == p4) continue;

			ll x = p2 * p2 * p4 * p4 * p4 * p4;

			rrep(k, s1) {
				ll p1k = P1[k];
				if (p1k == p2 || p1k == p4) continue;
				rep(l, k+1, s1) {
					ll p1l = P1[l];
					if (p1l == p2 || p1l == p4) continue;

					ll y = p1k * p1l;
					if (x >= LIM / y) break;

					ll z = x * y;

					if (check36(z)) {
						out(z-36);
						return;
					}
				}
			}

			rep(k, s3) {
				ll p3 = P3[k];
				if (p3 == p2 || p3 == p4) continue;

				ll y = p3 * p3 * p3;
				if (x >= LIM / y) break;

				ll z = x * y;

				if (check36(z)) {
					out(z-36);
					return;
				}
			}

		}
	}
}

signed main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	Main();
	return 0;
}
'''
yukicoder

結果

テストケース

ソースコード
