Submission #16942776
Source Code Expand
Copy
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <bitset> using namespace std; #ifdef LOCAL #define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr); #else #define eprintf(...) 42 #endif using ll = long long; using ld = long double; using uint = unsigned int; using ull = unsigned long long; template<typename T> using pair2 = pair<T, T>; using pii = pair<int, int>; using pli = pair<ll, int>; using pll = pair<ll, ll>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second clock_t startTime; double getCurrentTime() { return (double)(clock() - startTime) / CLOCKS_PER_SEC; } ll euclid(ll x, ll y, ll &k, ll &l) { if (y == 0) { k = 1; l = 0; return x; } ll g = euclid(y, x % y, l, k); l -= k * (x / y); return g; } int main() { startTime = clock(); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); ll n; scanf("%lld", &n); ll ans = 2 * n; vector<ll> d; for (ll x = 2; x * x <= n; x++) { if (n % x) continue; ll y = 1; while(n % x == 0) { n /= x; y *= x; } d.push_back(y); } if (n > 1) d.push_back(n); bool ok = false; for (int i = 0; i < (int)d.size(); i++) { if (d[i] % 2 == 0) { d[i] *= 2; ok = true; } } if (!ok) d.push_back(2); int m = (int)d.size(); assert(m < 18); for (int mask = 0; mask < (1 << m); mask++) { ll x = 1, y = 1; for (int i = 0; i < m; i++) { if ((mask >> i) & 1) x *= d[i]; else y *= d[i]; } if (y == 1) continue; ll k, l; assert(euclid(x, y, k, l) == 1); l %= x; if (l <= 0) l += x; k = l * y - 1; ans = min(ans, k); } printf("%lld\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Sum is Multiple |
User | Um_nik |
Language | C++ (GCC 9.2.1) |
Score | 600 |
Code Size | 2202 Byte |
Status | AC |
Exec Time | 271 ms |
Memory | 3708 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:71:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] 71 | scanf("%lld", &n); | ~~~~~^~~~~~~~~~~~
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00-sample-01.txt, 00-sample-02.txt |
All | 00-sample-01.txt, 00-sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00-sample-01.txt | AC | 5 ms | 3648 KB |
00-sample-02.txt | AC | 2 ms | 3620 KB |
01-01.txt | AC | 2 ms | 3532 KB |
01-02.txt | AC | 23 ms | 3564 KB |
01-03.txt | AC | 2 ms | 3604 KB |
01-04.txt | AC | 24 ms | 3588 KB |
01-05.txt | AC | 67 ms | 3648 KB |
01-06.txt | AC | 12 ms | 3588 KB |
01-07.txt | AC | 73 ms | 3644 KB |
01-08.txt | AC | 6 ms | 3636 KB |
01-09.txt | AC | 4 ms | 3588 KB |
01-10.txt | AC | 243 ms | 3652 KB |
01-11.txt | AC | 228 ms | 3648 KB |
01-12.txt | AC | 249 ms | 3544 KB |
01-13.txt | AC | 263 ms | 3708 KB |
01-14.txt | AC | 207 ms | 3612 KB |
01-15.txt | AC | 271 ms | 3568 KB |
01-16.txt | AC | 184 ms | 3532 KB |
01-17.txt | AC | 115 ms | 3564 KB |
01-18.txt | AC | 9 ms | 3604 KB |
01-19.txt | AC | 2 ms | 3624 KB |
01-20.txt | AC | 2 ms | 3532 KB |
01-21.txt | AC | 2 ms | 3564 KB |
01-22.txt | AC | 2 ms | 3564 KB |
01-23.txt | AC | 2 ms | 3592 KB |
01-24.txt | AC | 2 ms | 3624 KB |
01-25.txt | AC | 2 ms | 3604 KB |
01-26.txt | AC | 2 ms | 3572 KB |
01-27.txt | AC | 2 ms | 3592 KB |
01-28.txt | AC | 2 ms | 3588 KB |
01-29.txt | AC | 6 ms | 3708 KB |
01-30.txt | AC | 5 ms | 3608 KB |
01-31.txt | AC | 3 ms | 3600 KB |
01-32.txt | AC | 4 ms | 3612 KB |
01-33.txt | AC | 3 ms | 3648 KB |
01-34.txt | AC | 9 ms | 3604 KB |
01-35.txt | AC | 4 ms | 3572 KB |
01-36.txt | AC | 4 ms | 3588 KB |
01-37.txt | AC | 2 ms | 3632 KB |
01-38.txt | AC | 4 ms | 3600 KB |
01-39.txt | AC | 5 ms | 3548 KB |
01-40.txt | AC | 2 ms | 3592 KB |