Monthly Training Farm - May 2017 B. operator1 ( Math )

https://oj.icpc.tw/contest/5/problem/B

Problem Description:
Define operator @ with following property:
To calculate a @ b, first we transform them into base 3, then apply addition without carry.
For example, 7 @ 8 = 21_3 @ 22_3 = 10_3 = 3.
Now you are given x and y, print x @ ( x + 1 ) @ ( x + 2 ) @ ... @ y.

Constraints:
0 ≤ x ≤ y ≤ 2147483647

Solution:
We know that it is doing some kind of sum modulo on each digit. Therefore we can calculate result of [ 1, y ] then subtract result of [ 1, x - 1 ]. It is also obvious that subtraction should be applied as a reverse operation of addition without carry, which always produces one exact result. To calculate prefix addition without carry of [ 1, x ], we will first transform x into base 3. We will notice that, digit at position k from the lowest digit occurs exactly x % pow( 3, k ) + 1 times. What's more, we only need to calculate contribution of this kind, because contributions of other types naturally form sum of multiple of 3, which could be discarded.
However, there are 2 exceptions, one is that when calculating prefix addition, if the lowest digit is 2, it should be ignored because the 1 before that will cover it; the other is that when subtracting prefix from another prefix, beware that x - 1 might be negative.

Time Complexity:
O( log Y )

#include <bits/stdc++.h>
using namespace std;

#define int long long

int solve( int x ) { // [ 1, x ]
  vector< int > s;
  for( int i = x; i; i /= 3 ) {
    s.emplace_back( i % 3 );
  }
  int res = 0;
  for( int i = 0, t = 1; i < s.size(); ++i, t *= 3 ) {
    if( i == 0 and s[ i ] == 2 ) continue;
    res += 1LL * ( x % t + 1 ) * s[ i ] % 3 * t;
  }
  return res;
}

int apply( int x, int y ) { // x - y
  vector< int > a;
  for( int i = x; i; i /= 3 ) {
    a.emplace_back( i % 3 );
  }
  vector< int > b;
  for( int i = y; i; i /= 3 ) {
    b.emplace_back( i % 3 );
  }
  while( a.size() < b.size() ) a.emplace_back( 0 );
  while( b.size() < a.size() ) b.emplace_back( 0 );
  int res = 0;
  for( int i = 0, t = 1; i < a.size(); ++i, t *= 3 ) {
    if( a[ i ] == 0 ) {
      if( b[ i ] == 1 ) res += t * 2;
      if( b[ i ] == 2 ) res += t;
    } else if( a[ i ] == 1 ) {
      if( b[ i ] == 0 ) res += t;
      if( b[ i ] == 2 ) res += t * 2;
    } else {
      if( b[ i ] == 0 ) res += t * 2;
      if( b[ i ] == 1 ) res += t;
    }
  }
  return res;
}

signed main() {
  ios::sync_with_stdio( 0 );
  int x, y;
  cin >> x >> y;
  if( x == 0 ) {
    cout << solve( y ) << endl;
  } else {
    cout << apply( solve( y ), solve( x - 1 ) ) << endl;
  }
  return 0;
}