fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll; // Dùng long long để chứa số lớn
  5.  
  6. void solve(){
  7.     int n;
  8.     cin >> n;
  9.  
  10.     // Dùng Queue để duyệt BFS (Tìm số nhỏ nhất trước)
  11.     queue<ll> q;
  12.     q.push(9); // Bắt đầu bằng số 9
  13.  
  14.     while(!q.empty()){
  15.         ll top = q.front();
  16.         q.pop();
  17.  
  18.         // Kiểm tra chia hết
  19.         if(top % n == 0){
  20.             cout << top << "\n";
  21.             return; // Tìm thấy là dừng ngay, đây chắc chắn là số nhỏ nhất
  22.         }
  23.  
  24.         // Sinh ra 2 số tiếp theo: thêm 0 và thêm 9
  25.         // Chỉ push nếu số chưa quá lớn (tránh tràn long long)
  26.         if(top <= 1e17) { // 1e17 là giới hạn an toàn cho long long
  27.             q.push(top * 10);      // Nhánh thêm 0
  28.             q.push(top * 10 + 9);  // Nhánh thêm 9
  29.         }
  30.     }
  31. }
  32.  
  33. int main(){
  34.     ios_base::sync_with_stdio(false);
  35.     cin.tie(0);
  36.  
  37.     int t;
  38.     cin >> t;
  39.     while(t--){
  40.         solve();
  41.     }
  42. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
1
432
stdout
copy 
9990000
https://ideone.com/dWEJ6t
language:
C++14 (gcc 8.3)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!