FreakSkipper

D. Último dígito não-zero

Oct 30th, 2020 (edited)
807
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define vi vector<int>
  6. #define ll long long
  7. #define pb push_back
  8. #define eb emplace_back
  9. #define mp make_pair
  10. #define ii pair<int, int>
  11.  
  12. vi fatora(int n) {
  13.     vi ans;
  14.  
  15.     for (int i = 2; i * i <= n; i++) {
  16.         while (n % i == 0) {
  17.             n = n / i;
  18.             ans.eb(i);
  19.         }
  20.     }
  21.     if (n > 1) ans.eb(n);
  22.  
  23.     return ans;
  24. }
  25.  
  26. int main() {
  27.     int m, n;
  28.  
  29.     scanf("%d %d", &n, &m);
  30.  
  31.     if (n == 0) {
  32.         printf("1\n");
  33.         return EXIT_SUCCESS;
  34.     }
  35.  
  36.     int res = 1;
  37.     int dif = n - m;
  38.     int fator2 = 0, fator5 = 0;
  39.  
  40.     for (int i = dif + 1; i <= n; i++) {
  41.         int aux = i;
  42.  
  43.         for (int x = 2; x * x <= i; x++) {
  44.             while (aux % x == 0) {
  45.                 aux = aux / x;
  46.  
  47.                 if (x == 2)
  48.                     fator2++;
  49.                 else if (x == 5)
  50.                     fator5++;
  51.                 else
  52.                     res = res * x % 10;
  53.             }
  54.         }
  55.         if (aux > 1) {
  56.             if (aux == 2)
  57.                 fator2++;
  58.             else if (aux == 5)
  59.                 fator5++;
  60.             else
  61.                 res = res * aux % 10;
  62.         }
  63.     }
  64.  
  65.     while (true) {
  66.         if (fator2 > fator5) {
  67.             res = res * 2 % 10;
  68.             fator2--;
  69.         } else if (fator2 < fator5) {
  70.             res = res * 5 % 10;
  71.             fator5--;
  72.         } else
  73.             break;
  74.     }
  75.  
  76.     printf("%d", res);
  77.  
  78.     return EXIT_SUCCESS;
  79. }
RAW Paste Data