題意
給定一個數字 K（1 ≤ K ≤ 105），求一個最小的數字 N 的數字位數，N 各位數字都是 1，並且 N 能夠被 K 整除。如果這樣的 N 不存在，返回 -1。
題解
考慮特殊情況
假設 K 是偶數，由於 N 是奇數，N 一定不能被 K 整除，返回 -1。
假設 K 是 5 的倍數，N 也一定不能被 K 整除，因爲如果一個數字包含 5 這個因子，它末尾數一定是 0 或者 5。
考慮一般情況
此時 K 的因子不包含 2 和 5。
對於一個數字 N（長度爲 m，每一位都是 1），那麼 N = 1 + 101 + 102 + ... + 10m-1。 N % m = (1 + 101 + 102 + ... + 10m-1) % m = (1%m + 101%m + 102%m + ... + 10m-1%m) % m，我們需要 N % m = 0，但是這個數字可能很大，數字多長也不知道，我們只能枚舉 N 的長度，然後計算 %m 後的餘數。
猜測最多是不是只需要枚舉 K 次呢？記〔1, 11, 111, ..., 11....1（K個1）〕爲〔a1, a2, a3, ..., aK〕，猜測這個數列中，一定有某個數 as % m = 0。
假設 as 不存在，也就是這 K 這個數字都不能被 K 整除，由於他們被 K 除後的餘數都在〔0, K-1〕之間，應用鴿巢原理，一定有兩個數被 K 除後餘數相同，設它們爲 ai , aj （i < j），那麼 (aj - ai) % m = 0，考慮 aj - ai 的數字表示：前面有 j-i 個 1，後面有 i 個 0，即： aj-i * 10i ，也就是說 aj-i * 10i 能夠被 K 整除，由於 K 的因子不包含 2、5，所以 aj-i 一定能夠被 K 整除。也就是說，原來的數列中能夠被 K 整除的數字存在，這和假設矛盾。
所以只需要考慮最多 K 個數字即可。
1 // ================================================== 2 3 // C library 4 #include <cassert> 5 #include <cmath> 6 #include <climits> 7 #include <cstdio> 8 #include <cstdlib> 9 #include <cstring> 10 #include <cctype> 11 #include <ctime> 12 13 // Containers 14 #include <vector> 15 #include <list> 16 #include <stack> 17 #include <queue> 18 #include <deque> 19 #include <set> 20 #include <map> 21 #include <unordered_set> 22 #include <unordered_map> 23 24 // Input/Output 25 #include <iostream> 26 #include <istream> 27 #include <ostream> 28 #include <sstream> 29 #include <fstream> 30 #include <ios> 31 #include <iomanip> 32 33 // Other 34 #include <tuple> 35 #include <string> 36 #include <tuple> 37 #include <bitset> 38 #include <algorithm> 39 #include <utility> 40 #include <type_traits> 41 #include <iterator> 42 #include <limits> 43 #include <stdexcept> 44 #include <random> 45 #include <chrono> 46 47 // ================================================== 48 49 using namespace std; 50 51 // constants 52 const double EPS = 1e-9; 53 54 // type alias 55 using PII = pair<int, int>; 56 using LL = long long int; 57 using VI = vector<int>; 58 using VC = vector<char>; 59 using VS = vector<string>; 60 using VVI = vector<VI>; 61 using MII = map<int, int>; 62 using MCI = map<char, int>; 63 using SI = set<int>; 64 65 // ================================================== 66 67 // fast IO 68 static auto __2333__ = []() { 69 ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }(); 70 71 // ================================================== 72 73 // some macro for less typing 74 #define max_(x, y) ((x) > (y) ? (x) : (y)) 75 #define min_(x, y) ((x) > (y) ? (y) : (x)) 76 77 #define REP(i, n) for (int i = 0; i < int(n); ++i) // [0, n) 78 #define REPV(i, n) for (int i = int(n - 1); i >= 0; --i) // reverse [0, n) 79 #define FOR(i, a, b) for (int i = int(a); i < int(b); ++i) // [a, b) 80 #define DWN(i, b, a) for (int i = int(b - 1); i >= int(a); --i) // reverse [a, b) 81 82 #define REP_1(i, n) for (int i = 1; i <= int(n); ++i) // [1, n] 83 #define REPV_1(i, n) for (int i = int(n); i >= 1; --i) // reverse [1, n] 84 #define FOR_1(i, a, b) for (int i = int(a); i <= int(b); ++i) // [a, b] 85 #define DWN_1(i, b, a) for (int i = int(b); i >= a; --i) // reverse [a, b] 86 87 // DEBUG PRINT macro 88 #define PR(x) cout << #x " = " << (x) << " " 89 #define NL cout << " " 90 91 #define PR1(x) PR(x), NL 92 #define PR2(x1, x2) PR(x1), PR1(x2) 93 #define PR3(x1, x2, x3) PR(x1), PR2(x2, x3) 94 #define PR4(x1, x2, x3, x4) PR(x1), PR3(x2, x3, x4) 95 96 int direction[8][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, 97 {-1, -1}, {-1, 1}, {1, -1}, {1, 1} }; 98 99 // ================================================== 100 101 // simplest print 102 template<typename T> 103 void PRC(const T& a) { cout << a << " "; } 104 105 // print container 106 template<typename T> 107 void PRCO(const T& c) { for (auto x : c) PRC(x); NL; } 108 109 // print vector 110 template<typename T> 111 void PRV(const vector<T>& c) { PRCO<vector<T>>(c); } 112 113 // print C-style array 114 template<typename T, size_t N> 115 void PRA(const T (&ar)[N]) { 116 for (auto x : ar) PRC(x); NL; 117 } 118 119 // print pair 120 template<typename T1, typename T2> 121 void PRP(const pair<T1, T2>& p) { PRC(p.first); PRLN(p.second); } 122 123 // print a value and a new line 124 template<typename T> 125 void PRLN(const T& a) { cout << a << " "; } 126 127 // ================================================== 128 // math 129 bool is_prime(LL x) 130 { 131 if (x == 1) return false; 132 assert(x > 1); 133 LL m = ceil(sqrt(x)); 134 FOR_1(i, 2, m) { if (!(x % i)) return false; } 135 return true; 136 } 137 138 // prime table 139 const int PRIME_MAX = 10; 140 VI prime_table; 141 vector<bool> prime_table_bool(PRIME_MAX, true); 142 143 void get_prime() { 144 FOR_1(i, 2, PRIME_MAX) { 145 if (prime_table_bool[i]) { 146 prime_table.push_back(i); 147 for (int j = i << 1; j <= PRIME_MAX; j += i) prime_table_bool[j] = false; 148 } 149 } 150 } 151 152 // double equals 153 bool eq(double a, double b) { return fabs(a - b) < EPS; } 154 155 double random_() { 156 // generate random number in [0, 1] 157 return double(rand()) / RAND_MAX; 158 } 159 160 int random_(int m) { 161 // generate random int between [0, m - 1] 162 return int(random_() * (m - 1) + 0.5); 163 } 164 165 // high precision integer 166 167 class BNI { 168 friend ostream &operator<<(ostream &, const BNI &); 169 friend istream &operator>>(istream &, BNI &); 170 public: 171 BNI() = default; 172 BNI(const string &s) { *this = s; } 173 BNI(const char s[]) :BNI(string(s)) {} 174 BNI(const BNI &rhs) = default; 175 BNI(const LL n) { *this = n; }; 176 BNI(istream &in) { string s; in >> s; *this = s; } 177 178 BNI &operator=(const BNI &rhs) = default; 179 BNI &operator=(const string &s) { 180 string s_ = clean_zero_str(s); 181 num.resize(s_.size()); 182 int i = 0; 183 for (auto it = s_.crbegin(); it != s_.crend(); ++it) 184 num[i++] = *it - '0'; 185 return *this; 186 } 187 BNI &operator=(const char s[]) { 188 operator=(string(s)); 189 return *this; 190 } 191 BNI &operator=(LL n) { 192 stringstream ss; ss << n; 193 string s; ss >> s; 194 *this = s; 195 return *this; 196 } 197 BNI operator+(const BNI &rhs) const { 198 BNI res; 199 size_t max_len = max_(num.size(), rhs.num.size()); 200 int x; 201 for (int i = 0, rem = 0; rem || i < max_len; ++i) { 202 x = rem; 203 if (i < num.size()) x += num[i]; 204 if (i < rhs.num.size()) x += rhs.num[i]; 205 res.num.push_back(x % 10); 206 rem = x / 10; 207 } 208 res.clean_zero(); 209 return res; 210 } 211 BNI& operator+=(const BNI &rhs) { 212 *this = *this + rhs; 213 return *this; 214 } 215 BNI operator*(const BNI &rhs) const { 216 BNI res; 217 size_t sum_len = num.size() + rhs.num.size(); 218 res.num.resize(sum_len); 219 for (size_t i = 0; i < num.size(); ++i) { 220 for (size_t j = 0; j < rhs.num.size(); ++j) { 221 res.num[i + j] += num[i] * rhs.num[j]; 222 } 223 } 224 for (size_t i = 0; i < res.num.size() - 1; ++i) { 225 res.num[i + 1] += res.num[i] / 10; 226 res.num[i] %= 10; 227 } 228 res.clean_zero(); 229 return res; 230 } 231 BNI& operator*=(const BNI &rhs) { 232 *this = *this * rhs; 233 return *this; 234 } 235 /* 236 * assume *this >= rhs 237 */ 238 BNI operator-(const BNI &rhs) const { 239 assert(*this >= rhs); 240 if (rhs == 0LL) return *this; 241 BNI res; 242 int x; 243 for (int i = 0, rem = 0; i < num.size(); ++i) { 244 x = num[i] - rem; 245 if (i < rhs.num.size()) x -= rhs.num[i]; 246 if (x >= 0) rem = 0; 247 else { rem = 1; x += 10; } 248 res.num.push_back(x); 249 } 250 res.clean_zero(); 251 return res; 252 } 253 BNI& operator-=(const BNI &rhs) { 254 *this = *this - rhs; 255 return *this; 256 } 257 /* 258 * assume rhs is not zero 259 */ 260 pair<BNI, BNI> operator/(const BNI &rhs) const { 261 assert(BNI(0LL) != rhs); 262 if (*this < rhs) return make_pair(0LL, *this); 263 264 BNI quotient, rem; 265 string nume = c_str(); 266 string numerator = nume.substr(0, rhs.num.size()); 267 size_t pos = rhs.num.size(); 268 vector<BNI> times(10); 269 for (int i = 0; i < 10; ++i) times[i] = rhs * i; 270 string quot; 271 272 while (pos <= nume.size()) { 273 BNI nume_b = numerator; 274 int cnt = 0; 275 276 while (cnt < 10 && times[cnt] <= nume_b) ++cnt; 277 --cnt; 278 279 quot += char(cnt + '0'); 280 rem = nume_b - times[cnt]; 281 282 if (pos < nume.size()) 283 numerator = rem.c_str() + nume[pos]; 284 285 ++pos; 286 } 287 288 quotient = quot; 289 290 return make_pair(quotient, rem); 291 } 292 bool operator<(const BNI &rhs) const { 293 if (num.size() == 0) return !(rhs.num.size() == 0); 294 if (num.size() != rhs.num.size()) { 295 return num.size() < rhs.num.size(); 296 } 297 for (int i = num.size() - 1; i >= 0; --i) { 298 if (num[i] != rhs.num[i]) return num[i] < rhs.num[i]; 299 } 300 return false; 301 } 302 bool operator>(const BNI &rhs) const { return rhs < *this; } 303 bool operator<=(const BNI &rhs) const { return !(*this > rhs); } 304 bool operator>=(const BNI &rhs) const { return !(*this < rhs); } 305 bool operator!=(const BNI &rhs) const { return (*this < rhs) || (*this > rhs); } 306 bool operator==(const BNI &rhs) const { return !(*this != rhs); } 307 size_t size() const { return num.size(); } 308 string c_str() const { 309 string s; 310 for (auto x : num) s = char(x + '0') + s; 311 return s.empty() ? "0" : s; 312 } 313 void left_shift() { 314 if (!num.empty()) num.pop_back(); 315 } 316 protected: 317 vector<int> num; 318 string clean_zero_str(const string &s) { 319 if (s.empty() || s[0] != '0') return s; 320 size_t i = 0; 321 while (i < s.size() && '0' == s[i]) ++i; 322 return s.substr(i); 323 } 324 void clean_zero() { 325 for (auto it = num.rbegin(); it != num.rend() && *it == 0;) { 326 ++it; 327 num.pop_back(); 328 } 329 } 330 }; 331 332 ostream &operator<<(ostream &out, const BNI &x) { 333 out << x.c_str(); 334 return out; 335 } 336 337 istream &operator>>(istream &in, BNI &x) { 338 x = BNI(in); 339 return in; 340 } 341 342 // high precision float 343 class BNF : protected BNI { 344 friend ostream &operator<<(ostream &out, const BNF &x); 345 friend istream &operator>>(istream &in, BNF &x); 346 public: 347 BNF() = default; 348 BNF(const string &s) { *this = s; } 349 BNF(const char s[]): BNF(string(s)) {} 350 BNF(const BNF &rhs) = default; 351 BNF(const LL n) { *this = n; } 352 BNF(istream &in) { string s; in >> s; *this = s; } 353 354 BNF &operator=(const string &s) { 355 string s_ = clean_zero_str(s); 356 num.resize(s_.size()); 357 int i = 0; 358 for (auto it = s_.crbegin(); it != s_.crend(); ++it) 359 num[i++] = *it - '0'; 360 return *this; 361 } 362 BNF &operator=(const char s[]) { 363 operator=(string(s)); return *this; 364 } 365 BNF &operator=(LL n) { 366 stringstream ss; ss << n; 367 string s; ss >> s; 368 *this = s; 369 return *this; 370 } 371 BNF operator+(const BNF &rhs) const { 372 pair<string, string> in_fr1 = split(), in_fr2 = rhs.split(); 373 string inte1 = in_fr1.first, frac1 = in_fr1.second, 374 inte2 = in_fr2.first, frac2 = in_fr2.second; 375 LL inc = 0LL; 376 BNI frac_sum; 377 inc += sum_has_carry(frac1, frac2, frac_sum); 378 BNI inte_sum = BNI(inte1) + inte2 + inc; 379 380 return join_inte_frac(inte_sum, frac_sum); 381 } 382 BNF& operator+=(const BNF &rhs) { 383 *this = *this + rhs; 384 return *this; 385 } 386 /* 387 * assume *this >= rhs 388 */ 389 BNF operator-(const BNF &rhs) const { 390 assert(*this >= rhs); 391 pair<string, string> in_fr1 = split(), in_fr2 = rhs.split(); 392 string inte1 = in_fr1.first, frac1 = in_fr1.second, 393 inte2 = in_fr2.first, frac2 = in_fr2.second; 394 LL dec = 0LL; 395 if (BNI(frac1) < frac2) { 396 frac1 = '1' + frac1; ++dec; 397 } 398 while (frac1.size() < frac2.size()) frac1 += '0'; 399 while (frac2.size() < frac1.size()) frac2 += '0'; 400 BNI frac = BNI(frac1) - frac2; 401 BNI inte = BNI(inte1) - dec - inte2; 402 return join_inte_frac(inte, frac); 403 } 404 BNF& operator-=(const BNF &rhs) { 405 return *this = *this - rhs; 406 } 407 BNF operator*(const BNF &rhs) const { 408 pair<string, string> in_fr1 = split(), in_fr2 = rhs.split(); 409 string inte1 = in_fr1.first, frac1 = in_fr1.second, 410 inte2 = in_fr2.first, frac2 = in_fr2.second; 411 BNI res = BNI(inte1 + frac1) * (inte2 + frac2); 412 int deci = decimals + rhs.decimals; 413 string res_s = res.c_str(); 414 while (res_s.size() < deci) res_s = '0' + res_s; 415 return BNF(res_s.substr(0, res_s.size() - deci) + '.' 416 + res_s.substr(res_s.size() - deci)); 417 } 418 BNF& operator*=(const BNF &rhs) { 419 return *this = *this * rhs; 420 } 421 bool operator<(const BNF &rhs) const { 422 pair<string, string> in_fr1 = split(), in_fr2 = rhs.split(); 423 string inte1 = in_fr1.first, frac1 = in_fr1.second, 424 inte2 = in_fr2.first, frac2 = in_fr2.second; 425 if (inte1 < inte2) return true; 426 else if (inte1 == inte2) return frac1 < frac2; 427 else return false; 428 } 429 bool operator>(const BNF &rhs) const { return rhs < *this; } 430 bool operator<=(const BNF &rhs) const { return !(*this > rhs); } 431 bool operator>=(const BNF &rhs) const { return !(*this < rhs); } 432 bool operator!=(const BNF &rhs) const { return (*this < rhs) || (*this > rhs); } 433 bool operator==(const BNF &rhs) const { return !(*this != rhs); } 434 435 protected: 436 int decimals = 0; 437 LL sum_has_carry(const BNI &a, const BNI &b, BNI &sum) const { 438 int max_len = max_(a.size(), b.size()); 439 sum = a + b; 440 if (sum.size() > max_len) { sum.left_shift(); return 1LL; } 441 return 0LL; 442 } 443 BNF join_inte_frac(const BNI &inte, const BNI &frac) const { 444 return BNF(inte.c_str() + "." + frac.c_str()); 445 } 446 string clean_tail_zero_str(const string &s) { 447 int i = 0; 448 string r; 449 while (i < s.size() && '.' != s[i]) r += s[i++]; 450 451 int j = s.size() - 1; 452 while (j >= 0 && '0' == s[j]) --j; 453 for (int k = i + 1; k <= j; ++k) r += s[k]; 454 decimals = j >= i ? j - i : 0; 455 return r; 456 } 457 string clean_zero_str(const string &s) { 458 string r = BNI::clean_zero_str(s); 459 return clean_tail_zero_str(r); 460 } 461 string c_str() const { 462 string s; 463 for (int i = 0; i < num.size(); ++i) { 464 if (i == decimals) s = '.' + s; 465 s = char(num[i] + '0') + s; 466 } 467 if (s.empty()) s = "0"; 468 if (num.size() == decimals) s = '.' + s; 469 return s; 470 } 471 pair<string, string> split() const { 472 string s = c_str(); 473 size_t p = s.find('.'); 474 return make_pair(s.substr(0, p), s.substr(p + 1)); 475 } 476 }; 477 478 ostream &operator<<(ostream &out, const BNF &x) { 479 cout << x.c_str(); return out; 480 } 481 482 istream &operator>>(istream &in, BNF &x) { 483 x = BNF(in); return in; 484 } 485 486 // Trie Tree 487 const int ALPHASIZE = 26; 488 489 class TrieNode { 490 public: 491 TrieNode() 492 :wordEnd{false}, cnt{1} 493 { 494 REP(i, ALPHASIZE) { child[i] = nullptr; } 495 } 496 ~TrieNode() {} 497 void insert(string word) { 498 int i; 499 TrieNode *cur = this; 500 for (auto x:word) { 501 i = x - 'a'; 502 if (nullptr == cur->child[i]) { 503 cur->child[i] = new TrieNode(); 504 cur = cur->child[i]; 505 } else { 506 cur = cur->child[i]; 507 ++cur->cnt; 508 } 509 } 510 cur->wordEnd = true; 511 } 512 bool search(string word) { 513 int i; 514 TrieNode *cur = this; 515 for (auto x:word) { 516 i = x - 'a'; 517 if (nullptr == cur->child[i]) { 518 return false; 519 } 520 cur = cur->child[i]; 521 } 522 return cur->wordEnd; 523 } 524 int cnt_words(string word) { 525 int i; TrieNode *cur = this; 526 for(auto x:word) { 527 i = x - 'a'; 528 if (nullptr == cur->child[i]) return 0; 529 cur = cur->child[i]; 530 } 531 return cur->cnt; 532 } 533 TrieNode *child[ALPHASIZE]; 534 bool wordEnd; 535 int cnt; // number of words with the prefix 536 }; 537 538 539 540 // ================================================== 541 542 543 class Solution { 544 public: 545 int smallestRepunitDivByK(int K) { 546 if (K%2==0 || K%5==0) return -1; 547 int rem=1,cnt=1; 548 REP(i, K) { 549 if (rem%K==0) return cnt; 550 rem=(rem*10+1) % K; 551 cnt++; 552 } 553 return cnt; 554 } 555 }; 556 557 int main( void ) { 558 559 #ifdef DEBUG 560 freopen("b.in", "r", stdin); 561 #endif 562 563 Solution sol; 564 int a; 565 while (cin >> a) { 566 PRLN(sol.smallestRepunitDivByK(a)); 567 } 568 569 return 0; 570 }
end.