Submission #1697402
Source Code Expand
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <random>
using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;
unordered_set<int> uset;
random_device rnd;
vector<int> primes;
long long pow_mod(long long a, long long b, long long mod) {
long long ret = 1;
while (b) {
if (b & 1) ret = (a * ret) % mod;
a = (a * a) % mod;
b /= 2;
}
return ret;
}
bool miller_labin(long long n, const int loopNum = 1000) {
if (n == 2) return true;
if (n < 2 || n % 2 == 0) return false;
long long d = n - 1;
while ((d & 1) == 0) d >>= 1;
REP(_, loopNum) {
int a = (rnd() % (n - 1)) + 1;
LL y = pow_mod(a, d, n);
LL t = d;
while (t != n - 1 && y != 1 && y != n - 1) {
y = (y * y) % n;
t <<= 1;
}
if (y != n - 1 && (t & 1) == 0) return false;
}
return true;
}
vector <int> sieve_of_eratosthenes(int n) {
vector <bool> is(n + 1, true);
vector <int> res;
is[0] = false;
is[1] = false;
for (int i = 2; i <= n; i++) {
if (is[i]) {
res.emplace_back(i);
for (int j = i * 2; j <= n; j += i) {
is[j] = false;
}
}
}
return res;
}
long long cnt = 0;
int divisible_num(long long n) {
if (n == 1) return 1;
int num = 1;
int ans = 1;
FORE(el, primes) {
if (el * el * el > n) break;
int cnt = 1;
while (n % el == 0) {
n /= el; cnt++;
}
ans *= cnt;
}
if (n == 1) ans *= 1;
else if (miller_labin(n)) ans *= 2;
else {
int nsq = sqrt(n);
if (nsq * nsq == n) ans *= 3;
else ans *= 4;
}
return ans;
}
vector<long long> divisor(long long n) {
vector<long long> ret;
if (n > 1) for(long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.emplace_back(i);
if (i != n / i && i != 1) ret.emplace_back(n / i);
}
}
return ret;
}
int check(VI v) {
assert(v.size() == 100);
set<int> se;
FORE(el, v) {
auto vec = divisor(el);
FORE(e2, vec) se.insert(e2);
}
return se.size() + 100;
}
int check(int n) {
auto vec = divisor(n);
int nn = 0;
FORE(el, vec) {
nn += FIND(uset, el);
uset.insert(el);
}
return (int)vec.size() - nn;
}
//#define deb
int main(void) {
int n = INF;
primes = sieve_of_eratosthenes(1000);
VI v;
VPII vp;
REP(i, (int)1e5 - (int)1e4) {
vp.EB(MP(divisible_num(n - i * 200), n - i * 200));
}
RSORT(vp);
REP(i, 100) {
#ifdef deb
v.EB(vp[i].second);
#else
printf("%d\n", vp[i].second);
#endif
}
#ifdef deb
cerr << check(v) << endl;
#endif
}
Submission Info
Submission Time |
|
Task |
A - 約数をたくさんつくろう! |
User |
sekiya9311 |
Language |
C++14 (Clang 3.8.0) |
Score |
0 |
Code Size |
4073 Byte |
Status |
TLE |
Exec Time |
10503 ms |
Memory |
512 KB |
Judge Result
Set Name |
test_01 |
Score / Max Score |
0 / 100000 |
Status |
|
Set Name |
Test Cases |
test_01 |
noinput.txt |
Case Name |
Status |
Exec Time |
Memory |
noinput.txt |
TLE |
10503 ms |
512 KB |