結果
問題 | No.1657 Sum is Prime (Easy Version) |
ユーザー |
|
提出日時 | 2021-08-27 22:03:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 378 ms / 2,000 ms |
コード長 | 3,956 bytes |
コンパイル時間 | 2,323 ms |
コンパイル使用メモリ | 200,704 KB |
最終ジャッジ日時 | 2025-01-24 03:04:39 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
/* J A I S H R E E R A M */#include <bits/stdc++.h>using namespace std;#ifdef LUCTIVUD#include <buggyBaby.hpp>pretty:: PrettyPrinter NonIterable;#define cerr cout#else#define _____error_____(...)#endif#pragma GCC optimize("O3,unroll-loops,trapv")#pragma GCC target("avx,avx2,fma,sse,sse2,sse3,sse4,popcnt,lzcnt")// #pragma GCC optimize "trapv"/* Snips */typedef long long lld; typedef unsigned long long llu;#define forn(I7, E4) for(lld I7=0ll; I7 < E4; (I7)+=1ll)#define forn1(I7, E4) for(lld I7=1ll; I7 < E4+1; (I7)+=1ll)#define len(v) ((int)((v).size()))#define all(x) (x).begin(), (x).end()#define rall(x) (x).rbegin(), (x).rend()#define f1 first#define s2 second/* Utils */const lld MOD = int(1e9) + 7;const lld &mod = MOD;const long double EPS = 1e-6;const lld inf = 2e18;struct custom_hash {static uint64_t splitmix64(uint64_t x) {// http://xorshift.di.unimi.it/splitmix64.cx += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}size_t operator()(uint64_t x) const {static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};signed pleaseAC(void) {#ifdef LUCTIVUD// auto end_time = std::chrono::high_resolution_clock::now();// std::chrono::duration<double> diff = end_time - start_time;// cerr << "Finished in : " << diff.count() << "\n";#endifreturn 0;}void IAmJustice(void) {ios_base::sync_with_stdio(false); cin.tie(0);cout.precision(10); cout << fixed;#ifdef LUCTIVUD// const auto start_time = std::chrono::high_resolution_clock::now();freopen("/home/luctivud/CPPractice/IO/Zinput.txt", "r", stdin);freopen("/home/luctivud/CPPractice/IO/Zoutput.txt", "w", stdout);#endifreturn;}/* This part should be outside the main in global paradigm. */const long long MAXN = (lld)(1e7) + 1ll; // MAXN Sizevector<long long >isPrime(MAXN , true); // checkIfPrimevector<long long >prime_numbers; // List of prime numbersvector<long long >smallest_prime_factor(MAXN); // smallest_prime_factor of a numbervoid manipulated_seive() {isPrime[0] = isPrime[1] = false ;prime_numbers.push_back(2);smallest_prime_factor[2] = 2ll;for (long long int i=4; i < MAXN ; i+=2) {isPrime[i] = false;smallest_prime_factor[i] = 2ll;}for (long long int i = 3; i < MAXN ; i+=2) {if (isPrime[i]) {prime_numbers.push_back(i);smallest_prime_factor[i] = i;}for (long long int j = 0; j < (int)prime_numbers.size() && i * prime_numbers[j] < MAXN && prime_numbers[j] <= smallest_prime_factor[i]; j++){isPrime[i * prime_numbers[j]] = false;smallest_prime_factor[i * prime_numbers[j]] = prime_numbers[j] ;}}}/* This should be called inside main. *//*:::::::::::::::::::::: LOGIC :::::::::::::::::::::::::*/void solveEachTest(int _TestCase) {// cout << "Case #" << _TestCase << ": ";lld a, b; cin >> a >> b;lld ans = 0ll;for (lld i = a; i <= b; i++) {for (lld j = i; j <= b; j++) {if (abs(i - j) > 2) break;lld num = ((j * (j + 1)) - (i * (i - 1))) / 2;if (isPrime[num]) {ans += 1;}}}cout << ans;return;}/*:::::::::::::::::::::/LOGIC:::::::::::::::::::::::::*/signed main() {IAmJustice();manipulated_seive();int _T0T4 = 1;// cin >> _T0T4;for (int _TestCase = 1; _TestCase <= _T0T4; _TestCase++) {solveEachTest(_TestCase);cout << "\n";}return pleaseAC();}/* ~~.?.?.?.*/