fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define ll long long
  6. #define el cout<<"\n"
  7. #define sz(x) (int)(x).size()
  8. #define all(x) (x).begin(),(x).end()
  9. #define f0(i,n) for(int i=0;i<n;i++)
  10. #define f1(i,n) for(int i=1;i<=n;i++)
  11. #define fz(i,a,n,z) for(int i=a;i<n;i+=z)
  12. #define rep(i,a,n,z) for(int i=a;i>n;i-=z)
  13. #define faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  14. #define file(name) freopen(name".inp","r",stdin);freopen(name".out","w",stdout);
  15. const int N = 1e6 + 5;
  16. int REV(int n) { // Đảo số 
  17.     int res = 0;
  18.     while (n != 0) {
  19.         res = res * 10 + n % 10;
  20.         n /= 10;
  21.     }
  22.     return res;
  23. }
  24. int longma(int n) { // đếm độ dài của một số
  25.     int d = 0;
  26.     while (n != 0) {n /= 10; d++;}
  27.     return d;
  28. }
  29. int ghep(int a, int b) { // Ghép a với b
  30.     return a * pow(10, longma(b)) + b;
  31. }
  32. vector<int> palindrome;
  33. void SinhPalin() { // Sinh số đối xứng
  34.     for (int i = 1; i <= 9999; ++i) {
  35.         int revI = REV(i); 
  36.         palindrome.push_back(ghep(i, revI));
  37.         for (int j = 1; j <= 9; ++j) { // cho j vào giữa hai số là i và REV(i)
  38.             palindrome.push_back(ghep(i * 10 + j, revI));
  39.         }
  40.     }
  41.     sort(all(palindrome));
  42. }
  43. bool checkprime(ll n) // Kiểm tra nguyên tố
  44. {
  45.     if (n == 2 || n == 3) return true;
  46.     if (n < 2 || n % 2 == 0 || n % 3 == 0) return false;
  47.     for (int i = 5; 1ll * i * i <= n; i += 6) {
  48.         if (n % i == 0 || n % (i + 2) == 0) return false;
  49.     }
  50.     return true;
  51. }
  52. vector<int> Prime;
  53. void SinhNguyenTo(int n) { // Sinh số nguyên tố
  54.     Prime.push_back(2);
  55.     for (int i = 3; i <= sqrt(n); i += 2) {
  56.         if (checkprime(i)) Prime.push_back(i);
  57.     }
  58. }
  59. int main() {
  60.     faster
  61.  
  62.     int a, b;
  63.     cin >> a >> b;
  64.     SinhNguyenTo(b);
  65.     SinhPalin();
  66.  
  67.     int left = lower_bound(all(palindrome), a) - palindrome.begin(); // Tìm số đối xứng đầu tiên lớn hơn hoặc bằng a
  68.     int right = upper_bound(all(palindrome), b) - palindrome.begin() - 1; // Tìm số đối xứng đầu tiên nhỏ hơn hoặc bằng b
  69.  
  70.     int n = Prime.size();
  71.     ll res = 0;
  72.  
  73.     for (int i = left; i <= right; ++i) {
  74.  
  75.         int j = 0, cntDiv = 0, x = palindrome[i]; // cntDiv: biến đếm ước
  76.  
  77.         while (cntDiv < 3 && j < n) { // khi ước đạt tới giá trị thỏa mãn thì dừng để tiết kiệm thời gian chạy
  78.             if (palindrome[i] % Prime[j] == 0) {
  79.                 while (palindrome[i] % Prime[j] == 0) {palindrome[i] /= Prime[j];}
  80.                 cntDiv++;
  81.             }
  82.             ++j;
  83.         }
  84.  
  85.         if (palindrome[i] > 1)  {cntDiv++;} // vì chạy đến sqrt(n) nên chưa chắc số đó đã về 1. Ví dụ: số 91 chỉ chia 7 = 13 là hết vòng lặp nên phải +1 ước nguyên tố 
  86.         if (cntDiv >= 3)        {res += x;} // Thỏa mãn đề bài thì ...
  87.     }
  88.  
  89.     cout << res;
  90.  
  91.  
  92.  
  93. }
  94. /*-----------------------END-----------------------*/
Success #stdin #stdout 0.66s 5288KB
comments (?)
stdin
copy 
1 1000000000
stdout
copy 
29538508010576
https://ideone.com/5KBP37
language:
C++14 (gcc 8.3)
created:
13 days 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!