fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define hash_mod 2305843009213717ll
  4. #define ttt 2305843009213717ll
  5. #define mod7 1000000007
  6. #define mod9 1000000009
  7. #define mod2 30000000
  8. #define pa(a,b) make_pair(a,b)
  9. #define f first
  10. #define s second
  11. #define pb(a)  push_back(a)
  12. #define all(a) a.begin() , a.end()
  13. #define mem(a, b) memset(a, b, sizeof(a))
  14. #define LL  long long int
  15. #define oo 1e9
  16. #define pi 3.141592653589793238
  17. #define eps  1e-6
  18.  
  19.  
  20. #define INF_MAX 2147483647
  21. #define INF_MIN -2147483647
  22. #define INF_LL 4000000000000000000LL
  23. #define INF 1000000000
  24. #define EPS 1e-8
  25. #define LL long long
  26. #define pb push_back
  27. #define f first
  28. #define s second
  29. #define setzero(a) memset(a,0,sizeof(a))
  30. #define setdp(a) memset(a,-1,sizeof(a))
  31. #define bits(a) __builtin_popcountll(a)
  32.  
  33. using namespace std;
  34.  
  35. const int base = 1000000000;
  36. const int base_digits = 9;
  37.  
  38. struct BigInt {
  39.   vector<int> a;
  40.   int sign;
  41.  
  42.   BigInt() :
  43.       sign(1) {
  44.   }
  45.  
  46.   BigInt(long long v) {
  47.     *this = v;
  48.   }
  49.  
  50.   BigInt(const string &s) {
  51.     read(s);
  52.   }
  53.  
  54.   void operator=(const BigInt &v) {
  55.     sign = v.sign;
  56.     a = v.a;
  57.   }
  58.  
  59.   void operator=(long long v) {
  60.     sign = 1;
  61.     if (v < 0)
  62.       sign = -1, v = -v;
  63.     for (; v > 0; v = v / base)
  64.       a.push_back(v % base);
  65.   }
  66.  
  67.   BigInt operator+(const BigInt &v) const {
  68.     if (sign == v.sign) {
  69.       BigInt res = v;
  70.  
  71.       for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry;
  72.           ++i) {
  73.         if (i == (int) res.a.size())
  74.           res.a.push_back(0);
  75.         res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
  76.         carry = res.a[i] >= base;
  77.         if (carry)
  78.           res.a[i] -= base;
  79.       }
  80.       return res;
  81.     }
  82.     return *this - (-v);
  83.   }
  84.  
  85.   BigInt operator-(const BigInt &v) const {
  86.     if (sign == v.sign) {
  87.       if (abs() >= v.abs()) {
  88.         BigInt res = *this;
  89.         for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
  90.           res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  91.           carry = res.a[i] < 0;
  92.           if (carry)
  93.             res.a[i] += base;
  94.         }
  95.         res.trim();
  96.         return res;
  97.       }
  98.       return -(v - *this);
  99.     }
  100.     return *this + (-v);
  101.   }
  102.  
  103.   void operator*=(int v) {
  104.     if (v < 0)
  105.       sign = -sign, v = -v;
  106.     for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  107.       if (i == (int) a.size())
  108.         a.push_back(0);
  109.       long long cur = a[i] * (long long) v + carry;
  110.       carry = (int) (cur / base);
  111.       a[i] = (int) (cur % base);
  112.       //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  113.     }
  114.     trim();
  115.   }
  116.  
  117.   BigInt operator*(int v) const {
  118.     BigInt res = *this;
  119.     res *= v;
  120.     return res;
  121.   }
  122.  
  123.   friend pair<BigInt, BigInt> divmod(const BigInt &a1, const BigInt &b1) {
  124.     int norm = base / (b1.a.back() + 1);
  125.     BigInt a = a1.abs() * norm;
  126.     BigInt b = b1.abs() * norm;
  127.     BigInt q, r;
  128.     q.a.resize(a.a.size());
  129.  
  130.     for (int i = a.a.size() - 1; i >= 0; i--) {
  131.       r *= base;
  132.       r += a.a[i];
  133.       int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  134.       int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  135.       int d = ((long long) base * s1 + s2) / b.a.back();
  136.       r -= b * d;
  137.       while (r < 0)
  138.         r += b, --d;
  139.       q.a[i] = d;
  140.     }
  141.  
  142.     q.sign = a1.sign * b1.sign;
  143.     r.sign = a1.sign;
  144.     q.trim();
  145.     r.trim();
  146.     return make_pair(q, r / norm);
  147.   }
  148.  
  149.   BigInt operator/(const BigInt &v) const {
  150.     return divmod(*this, v).first;
  151.   }
  152.  
  153.   BigInt operator%(const BigInt &v) const {
  154.     return divmod(*this, v).second;
  155.   }
  156.  
  157.   void operator/=(int v) {
  158.     if (v < 0)
  159.       sign = -sign, v = -v;
  160.     for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  161.       long long cur = a[i] + rem * (long long) base;
  162.       a[i] = (int) (cur / v);
  163.       rem = (int) (cur % v);
  164.     }
  165.     trim();
  166.   }
  167.  
  168.   BigInt operator/(int v) const {
  169.     BigInt res = *this;
  170.     res /= v;
  171.     return res;
  172.   }
  173.  
  174.   int operator%(int v) const {
  175.     if (v < 0)
  176.       v = -v;
  177.     int m = 0;
  178.     for (int i = a.size() - 1; i >= 0; --i)
  179.       m = (a[i] + m * (long long) base) % v;
  180.     return m * sign;
  181.   }
  182.  
  183.   void operator+=(const BigInt &v) {
  184.     *this = *this + v;
  185.   }
  186.   void operator-=(const BigInt &v) {
  187.     *this = *this - v;
  188.   }
  189.   void operator*=(const BigInt &v) {
  190.     *this = *this * v;
  191.   }
  192.   void operator/=(const BigInt &v) {
  193.     *this = *this / v;
  194.   }
  195.  
  196.   bool operator<(const BigInt &v) const {
  197.     if (sign != v.sign)
  198.       return sign < v.sign;
  199.     if (a.size() != v.a.size())
  200.       return a.size() * sign < v.a.size() * v.sign;
  201.     for (int i = a.size() - 1; i >= 0; i--)
  202.       if (a[i] != v.a[i])
  203.         return a[i] * sign < v.a[i] * sign;
  204.     return false;
  205.   }
  206.  
  207.   bool operator>(const BigInt &v) const {
  208.     return v < *this;
  209.   }
  210.   bool operator<=(const BigInt &v) const {
  211.     return !(v < *this);
  212.   }
  213.   bool operator>=(const BigInt &v) const {
  214.     return !(*this < v);
  215.   }
  216.   bool operator==(const BigInt &v) const {
  217.     return !(*this < v) && !(v < *this);
  218.   }
  219.   bool operator!=(const BigInt &v) const {
  220.     return *this < v || v < *this;
  221.   }
  222.  
  223.   void trim() {
  224.     while (!a.empty() && !a.back())
  225.       a.pop_back();
  226.     if (a.empty())
  227.       sign = 1;
  228.   }
  229.  
  230.   bool isZero() const {
  231.     return a.empty() || (a.size() == 1 && !a[0]);
  232.   }
  233.  
  234.   BigInt operator-() const {
  235.     BigInt res = *this;
  236.     res.sign = -sign;
  237.     return res;
  238.   }
  239.  
  240.   BigInt abs() const {
  241.     BigInt res = *this;
  242.     res.sign *= res.sign;
  243.     return res;
  244.   }
  245.  
  246.  
  247.   void read(const string &s) {
  248.     sign = 1;
  249.     a.clear();
  250.     int pos = 0;
  251.     while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  252.       if (s[pos] == '-')
  253.         sign = -sign;
  254.       ++pos;
  255.     }
  256.     for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  257.       int x = 0;
  258.       for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  259.         x = x * 10 + s[j] - '0';
  260.       a.push_back(x);
  261.     }
  262.     trim();
  263.   }
  264.  
  265.   friend istream& operator>>(istream &stream, BigInt &v) {
  266.     string s;
  267.     stream >> s;
  268.     v.read(s);
  269.     return stream;
  270.   }
  271.  
  272.   friend ostream& operator<<(ostream &stream, const BigInt &v) {
  273.     if (v.sign == -1)
  274.       stream << '-';
  275.     stream << (v.a.empty() ? 0 : v.a.back());
  276.     for (int i = (int) v.a.size() - 2; i >= 0; --i)
  277.       stream << setw(base_digits) << setfill('0') << v.a[i];
  278.     return stream;
  279.   }
  280.  
  281.   static vector<int> convert_base(const vector<int> &a, int old_digits,
  282.       int new_digits) {
  283.     vector<long long> p(max(old_digits, new_digits) + 1);
  284.     p[0] = 1;
  285.     for (int i = 1; i < (int) p.size(); i++)
  286.       p[i] = p[i - 1] * 10;
  287.     vector<int> res;
  288.     long long cur = 0;
  289.     int cur_digits = 0;
  290.     for (int i = 0; i < (int) a.size(); i++) {
  291.       cur += a[i] * p[cur_digits];
  292.       cur_digits += old_digits;
  293.       while (cur_digits >= new_digits) {
  294.         res.push_back(int(cur % p[new_digits]));
  295.         cur /= p[new_digits];
  296.         cur_digits -= new_digits;
  297.       }
  298.     }
  299.     res.push_back((int) cur);
  300.     while (!res.empty() && !res.back())
  301.       res.pop_back();
  302.     return res;
  303.   }
  304.  
  305.   typedef vector<long long> vll;
  306.  
  307.   static vll karatsubaMultiply(const vll &a, const vll &b) {
  308.     int n = a.size();
  309.     vll res(n + n);
  310.     if (n <= 32) {
  311.       for (int i = 0; i < n; i++)
  312.         for (int j = 0; j < n; j++)
  313.           res[i + j] += a[i] * b[j];
  314.       return res;
  315.     }
  316.  
  317.     int k = n >> 1;
  318.     vll a1(a.begin(), a.begin() + k);
  319.     vll a2(a.begin() + k, a.end());
  320.     vll b1(b.begin(), b.begin() + k);
  321.     vll b2(b.begin() + k, b.end());
  322.  
  323.     vll a1b1 = karatsubaMultiply(a1, b1);
  324.     vll a2b2 = karatsubaMultiply(a2, b2);
  325.  
  326.     for (int i = 0; i < k; i++)
  327.       a2[i] += a1[i];
  328.     for (int i = 0; i < k; i++)
  329.       b2[i] += b1[i];
  330.  
  331.     vll r = karatsubaMultiply(a2, b2);
  332.     for (int i = 0; i < (int) a1b1.size(); i++)
  333.       r[i] -= a1b1[i];
  334.     for (int i = 0; i < (int) a2b2.size(); i++)
  335.       r[i] -= a2b2[i];
  336.  
  337.     for (int i = 0; i < (int) r.size(); i++)
  338.       res[i + k] += r[i];
  339.     for (int i = 0; i < (int) a1b1.size(); i++)
  340.       res[i] += a1b1[i];
  341.     for (int i = 0; i < (int) a2b2.size(); i++)
  342.       res[i + n] += a2b2[i];
  343.     return res;
  344.   }
  345.  
  346.   BigInt operator*(const BigInt &v) const {
  347.     vector<int> a6 = convert_base(this->a, base_digits, 6);
  348.     vector<int> b6 = convert_base(v.a, base_digits, 6);
  349.     vll a(a6.begin(), a6.end());
  350.     vll b(b6.begin(), b6.end());
  351.     while (a.size() < b.size())
  352.       a.push_back(0);
  353.     while (b.size() < a.size())
  354.       b.push_back(0);
  355.     while (a.size() & (a.size() - 1))
  356.       a.push_back(0), b.push_back(0);
  357.     vll c = karatsubaMultiply(a, b);
  358.     BigInt res;
  359.     res.sign = sign * v.sign;
  360.     for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  361.       long long cur = c[i] + carry;
  362.       res.a.push_back((int) (cur % 1000000));
  363.       carry = (int) (cur / 1000000);
  364.     }
  365.     res.a = convert_base(res.a, 6, base_digits);
  366.     res.trim();
  367.     return res;
  368.   }
  369. };
  370.  
  371. BigInt big_gcd(BigInt a, BigInt b) {
  372.     return b == 0 ? a : big_gcd(b, a - (a / b) * b);
  373. }
  374. int main()
  375. {
  376.     int t; cin >> t ;
  377.     int c = 1 ;
  378.     while(t--){
  379.         cout << "Case #" << c++ << ": " ;
  380.  
  381.         BigInt n ; int l ;  cin >> n >> l ;
  382.  
  383.         vector<BigInt> vals ;
  384.  
  385.         for(int i = 0 ; i < l ; i++){
  386.             BigInt x; cin >> x ;
  387.             vals.pb(x) ;
  388.         }
  389.  
  390.         BigInt tmp = 0 ;
  391.         int pos = 0 ;
  392.         for(int i = 1 ; i < l ; i++){
  393.             if(vals[i - 1] != vals[i]){
  394.                 tmp = big_gcd(vals[i] , vals[i - 1]) ;
  395.                 pos = i + 1 ;
  396.                 break ;
  397.             }
  398.         }
  399.  
  400.  
  401.         vector<pair<BigInt , int> > a ;
  402.  
  403.         a.pb(pa(tmp , pos)) ;
  404.  
  405.         BigInt temp = tmp ;
  406.  
  407.         for(int i = pos - 1 ; i < l ; i++){
  408.             tmp = vals[i] / tmp ;
  409.             a.pb(pa(tmp , i + 2)) ;
  410.         }
  411.  
  412.         for(int i = pos - 2 ; i >= 0 ; i--){
  413.             temp = vals[i] / temp ;
  414.             a.pb(pa(temp , i + 1)) ;
  415.         }
  416.  
  417.         sort(all(a)) ;
  418.  
  419.         string ans = "" ;
  420.  
  421.         for(int i  = 0; i <= l ; i++){
  422.             ans += 'a' ;
  423.         }
  424.  
  425.         tmp = a[0].f ; char cur = 'A' ;
  426.  
  427.         for(int i = 0 ; i < a.size() ; i++){
  428.             if(tmp != a[i].f){
  429.                 ++cur ;
  430.                 tmp = a[i].f ;
  431.             }
  432.  
  433.             ans[a[i].s - 1] = cur ;
  434.         }
  435.  
  436.         cout << ans  << endl ;
  437.     }
  438. }
  439.  
Success #stdin #stdout 0s 15288KB
comments (?)
stdin
copy 
2
103 31
217 1891 4819 2291 2987 3811 1739 2491 4717 445 65 1079 8383 5353 901 187 649 1003 697 3239 7663 291 123 779 1007 3551 1943 2117 1679 989 3053
10000 25
3292937 175597 18779 50429 375469 1651121 2102 3722 2376497 611683 489059 2328901 3150061 829981 421301 76409 38477 291931 730241 959821 1664197 3057407 4267589 4729181 5335543
stdout
copy 
Case #1: CJQUIZKNOWBEVYOFDPFLUXALGORITHMS
Case #2: SUBDERMATOGLYPHICFJKNQVWXZ
https://ideone.com/f6NWUO
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!