結果

問題 No.1312 Snake Eyes
ユーザー 👑 AngrySadEightAngrySadEight
提出日時 2020-12-09 01:10:59
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 107 ms / 2,000 ms
コード長 13,497 bytes
コンパイル時間 2,025 ms
コンパイル使用メモリ 182,744 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 12:58:05
合計ジャッジ時間 6,557 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 2 ms
5,248 KB
testcase_30 AC 2 ms
5,248 KB
testcase_31 AC 2 ms
5,248 KB
testcase_32 AC 2 ms
5,248 KB
testcase_33 AC 2 ms
5,248 KB
testcase_34 AC 2 ms
5,248 KB
testcase_35 AC 2 ms
5,248 KB
testcase_36 AC 2 ms
5,248 KB
testcase_37 AC 2 ms
5,248 KB
testcase_38 AC 3 ms
5,248 KB
testcase_39 AC 5 ms
5,248 KB
testcase_40 AC 5 ms
5,248 KB
testcase_41 AC 5 ms
5,248 KB
testcase_42 AC 3 ms
5,248 KB
testcase_43 AC 5 ms
5,248 KB
testcase_44 AC 3 ms
5,248 KB
testcase_45 AC 4 ms
5,248 KB
testcase_46 AC 5 ms
5,248 KB
testcase_47 AC 3 ms
5,248 KB
testcase_48 AC 94 ms
5,248 KB
testcase_49 AC 85 ms
5,248 KB
testcase_50 AC 68 ms
5,248 KB
testcase_51 AC 35 ms
5,248 KB
testcase_52 AC 105 ms
5,248 KB
testcase_53 AC 79 ms
5,248 KB
testcase_54 AC 93 ms
5,248 KB
testcase_55 AC 46 ms
5,248 KB
testcase_56 AC 60 ms
5,248 KB
testcase_57 AC 60 ms
5,248 KB
testcase_58 AC 81 ms
5,248 KB
testcase_59 AC 31 ms
5,248 KB
testcase_60 AC 58 ms
5,248 KB
testcase_61 AC 104 ms
5,248 KB
testcase_62 AC 42 ms
5,248 KB
testcase_63 AC 3 ms
5,248 KB
testcase_64 AC 5 ms
5,248 KB
testcase_65 AC 13 ms
5,248 KB
testcase_66 AC 2 ms
5,248 KB
testcase_67 AC 2 ms
5,248 KB
testcase_68 AC 6 ms
5,248 KB
testcase_69 AC 2 ms
5,248 KB
testcase_70 AC 85 ms
5,248 KB
testcase_71 AC 52 ms
5,248 KB
testcase_72 AC 6 ms
5,248 KB
testcase_73 AC 2 ms
5,248 KB
testcase_74 AC 2 ms
5,248 KB
testcase_75 AC 2 ms
5,248 KB
testcase_76 AC 104 ms
5,248 KB
testcase_77 AC 106 ms
5,248 KB
testcase_78 AC 106 ms
5,248 KB
testcase_79 AC 80 ms
5,248 KB
testcase_80 AC 107 ms
5,248 KB
testcase_81 AC 106 ms
5,248 KB
testcase_82 AC 106 ms
5,248 KB
testcase_83 AC 106 ms
5,248 KB
testcase_84 AC 106 ms
5,248 KB
testcase_85 AC 98 ms
5,248 KB
testcase_86 AC 91 ms
5,248 KB
testcase_87 AC 52 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;
vector<ll> bitconversion(ll i, ll n, ll N){
//inN
//bitconversion(33,3,4)={1,0,2,0}
ll x = 1;
rep(j,N){
x *= n;
}
vector<ll> vec(N);
rep(j,N){
x /= n;
vec[j] = i / x;
i -= x * vec[j];
}
return vec;
}
int ctoi(char c){
//char1int
switch (c){
case '0': return 0;
case '1': return 1;
case '2': return 2;
case '3': return 3;
case '4': return 4;
case '5': return 5;
case '6': return 6;
case '7': return 7;
case '8': return 8;
case '9': return 9;
default: return 0;
}
}
vector<int> topological_sort(vector<vector<int> > &connection, vector<int> &count, int N){
//vector
//connection
//count
vector<int> ans(0);
queue<int> que;
for (int i = 0; i < N; i++){
if (count[i] == 0){
que.push(i);
}
}
while(que.size() != 0){
int v = que.front();
que.pop();
for (int i = 0; i < connection[v].size(); i++){
count[connection[v][i]] -= 1;
if (count[connection[v][i]] == 0){
que.push(connection[v][i]);
}
}
ans.push_back(v);
}
return ans;
}
struct union_find{
vector<int> par;
vector<int> rank;
vector<int> siz;
union_find(int N) : par(N), rank(N), siz(N){
rep(i,N){
par[i] = i;
rank[i] = 0;
siz[i] = 1;
}
}
//union_findunion_find tree(N)
int root(int x){
if (par[x] == x){
return x;
}
return par[x] = root(par[x]);
}
//
void unite(int x, int y){
int rx = root(x);
int ry = root(y);
if (rx == ry) return;
if (rank[rx] < rank[ry]){
par[rx] = ry;
siz[ry] += siz[rx];
}
else{
par[ry] = rx;
siz[rx] += siz[ry];
if (rank[rx] == rank[ry]) rank[rx]++;
}
}
//xy(rank)
//
bool same(int x, int y){
int rx = root(x);
int ry = root(y);
return rx == ry;
}
//xy
int size(int x){
return siz[root(x)];
}
//x
};
int gcd(int a, int b){
//ab
int r,temp;
if (a < b){
temp = a;
a = b;
b = temp;
}
while ( (r = a % b) != 0){
a = b;
b = r;
}
return b;
}
ll iterative_square_method(ll i, vector<ll> &vec, ll N, ll mod){
//iXmod
//XmoddividingNvector(vec)
//2100000mod1e9+7
//iterative_square_method(2,moddividing(100000,2,30),30,1000000007)
ll ans = 1;
rep(j,N){
if (vec[N - 1 - j] == 1) ans = (ans * i) % mod;
i = (i * i) % mod;
}
return ans;
}
ll moddividing(ll x,ll y){
//x÷ymod1e9+7
vector<ll> vec(30);
rep(i,30){
vec[i] = y;
y = y * y % 1000000007;
}
ll c = x;
c = c * vec[0] % 1000000007;
c = c * vec[2] % 1000000007;
c = c * vec[9] % 1000000007;
c = c * vec[11] % 1000000007;
c = c * vec[14] % 1000000007;
c = c * vec[15] % 1000000007;
c = c * vec[17] % 1000000007;
c = c * vec[19] % 1000000007;
c = c * vec[20] % 1000000007;
c = c * vec[23] % 1000000007;
c = c * vec[24] % 1000000007;
c = c * vec[25] % 1000000007;
c = c * vec[27] % 1000000007;
c = c * vec[28] % 1000000007;
c = c * vec[29] % 1000000007;
return c;
}
ll moddividing2(ll x,ll y){
//x÷ymod998244353
vector<ll> vec(30);
rep(i,30){
vec[i] = y;
y = y * y % 998244353;
}
ll c = x;
c = c * vec[0] % 998244353;
c = c * vec[1] % 998244353;
c = c * vec[2] % 998244353;
c = c * vec[3] % 998244353;
c = c * vec[4] % 998244353;
c = c * vec[5] % 998244353;
c = c * vec[6] % 998244353;
c = c * vec[7] % 998244353;
c = c * vec[8] % 998244353;
c = c * vec[9] % 998244353;
c = c * vec[10] % 998244353;
c = c * vec[11] % 998244353;
c = c * vec[12] % 998244353;
c = c * vec[13] % 998244353;
c = c * vec[14] % 998244353;
c = c * vec[15] % 998244353;
c = c * vec[16] % 998244353;
c = c * vec[17] % 998244353;
c = c * vec[18] % 998244353;
c = c * vec[19] % 998244353;
c = c * vec[20] % 998244353;
c = c * vec[21] % 998244353;
c = c * vec[22] % 998244353;
c = c * vec[24] % 998244353;
c = c * vec[25] % 998244353;
c = c * vec[27] % 998244353;
c = c * vec[28] % 998244353;
c = c * vec[29] % 998244353;
return c;
}
struct segtree{
//
vector<int> vec;
segtree(int N) : vec(N){
rep(i,N){
vec[i] = 0;
}
}
//vector
//N*22
void make(int k, int a, int N){ //0_indexed
k += (N / 2);
vec[k] = a;
}
//ka
void sum_update(int k, int a, int N){ //0_indexed
k += (N / 2);
vec[k] = a;
while(k > 1){
k = k / 2;
vec[k] = vec[k * 2] + vec[k * 2 + 1];
}
}
//ka
void max_update(int k, int a, int N){ //0_indexed
k += (N / 2);
vec[k] = a;
while(k > 1){
k = k / 2;
vec[k] = max(vec[k * 2], vec[k * 2 + 1]);
}
}
//ka
void min_update(int k, int a, int N){ //0_indexed
k += (N / 2);
vec[k] = a;
while(k > 1){
k = k / 2;
vec[k] = min(vec[k * 2], vec[k * 2 + 1]);
}
}
//ka
int min_query(int a, int b, int k, int l, int r){ // min_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
if (r <= a || b <= l) return 1000000000;
if (a <= l && r <= b) return vec[k];
int vl = min_query(a, b, k * 2, l, (l + r) / 2);
int vr = min_query(a, b, k * 2 + 1, (l + r) / 2, r);
return min(vl,vr);
}
//[a,b)(a,b0_indexed)
//k,l,rk=1,l=0,r=N/2
int check(int i){
return vec[i];
}
//i
int max_query(int a, int b, int k, int l, int r){ // max_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
if (r <= a || b <= l) return -1000000000;
if (a <= l && r <= b) return vec[k];
int vl = max_query(a, b, k * 2, l, (l + r) / 2);
int vr = max_query(a, b, k * 2 + 1, (l + r) / 2, r);
return max(vl,vr);
}
//[a,b)(a,b0_indexed)
//k,l,rk=1,l=0,r=N/2
int sum_query(int a, int b, int k, int l, int r){ // sum_query(a,b,1,0,N / 2) a,b,l,r=0_indexed
if (r <= a || b <= l) return 0;
if (a <= l && r <= b) return vec[k];
int vl = sum_query(a, b, k * 2, l, (l + r) / 2);
int vr = sum_query(a, b, k * 2 + 1, (l + r) / 2, r);
return vl + vr;
}
//[a,b)(a,b0_indexed)
//k,l,rk=1,l=0,r=N/2
};
char itoc(int c){
//int025c(c+1)char1
switch (c){
case 0: return 'a';
case 1: return 'b';
case 2: return 'c';
case 3: return 'd';
case 4: return 'e';
case 5: return 'f';
case 6: return 'g';
case 7: return 'h';
case 8: return 'i';
case 9: return 'j';
case 10: return 'k';
case 11: return 'l';
case 12: return 'm';
case 13: return 'n';
case 14: return 'o';
case 15: return 'p';
case 16: return 'q';
case 17: return 'r';
case 18: return 's';
case 19: return 't';
case 20: return 'u';
case 21: return 'v';
case 22: return 'w';
case 23: return 'x';
case 24: return 'y';
case 25: return 'z';
default: return 'a';
}
}
int vector_finder(vector<int> &vec, int number){
//intvectorO(len(vec))
//10
int len = vec.size();
int cnt = 0;
rep(i,len){
if (vec[i] == number) cnt++;
}
if (cnt >= 1) return 1;
else return 0;
}
int vector_finder_rapid(vector<int> &vec, int number){
//vector_finderO(log(len(vec)))
//vector
int len = vec.size();
int cnt = -1;
int left = 0;
int right = len - 1;
if (vec[left] > number) cnt += 1;
else if (vec[right] < number) cnt += 1;
else if (vec[left] == number) cnt += 2;
else if (vec[right] == number) cnt += 2;
else{
while(true){
if (right - left == 1){
if (vec[left] == number) cnt += 2;
else cnt += 1;
break;
}
else{
if (vec[(left + right) / 2] <= number){
left = (left + right) / 2;
}
else{
right = (left + right) / 2;
}
}
}
}
return cnt;
}
void vector_print(vector<ll> &vec){
//vector
int len = vec.size();
rep(i,len - 1){
cout << vec[i] << " ";
}
cout << vec[len - 1] << endl;
}
void vector_print2(vector<int> &vec){
//vector
int len = vec.size();
rep(i,len){
cout << vec[i] << endl;
}
}
void vector_print3(vector<vector<int> > &vec){
//vector
int len1 = vec.size();
rep(i,len1){
int len2 = vec[i].size();
rep(j,len2 - 1){
cout << vec[i][j] << " ";
}
cout << vec[i][len2 - 1] << endl;
}
}
int main(){
ll N;
cin >> N;
vector<pair<ll,ll> > isdivisor(0);
for (ll i = 1; i * i < N; i++){
if (N % i == 0){
isdivisor.push_back(pair<ll,ll> (i, N / i));
}
}
ll min_ans = N;
for (ll i = 2; i * i < N; i++){
ll times = 1;
ll num = 1;
while(true){
if (num * i > N){
break;
}
else{
num *= i;
times++;
}
}
vector<ll> bin = bitconversion(N,i,times);
bool same = true;
ll first_num = bin[0];
for (ll j = 0; j < times; j++){
if (first_num != bin[j]) same = false;
}
if (same) min_ans = min(min_ans,i);
}
for (ll i = 0; i < isdivisor.size(); i++){
if (isdivisor[i].second - isdivisor[i].first >= 2) min_ans = min(min_ans, isdivisor[i].second - 1);
}
if (N == 1) cout << 2 << endl;
else if (N == 2) cout << 3 << endl;
else cout << min_ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0