c++ - Computing Nth triangular number that is also a square number -

this problem came out in practice contest:

compute nth triangular number square number, modulo 10006699. (1 ≤ n ≤ 10^18) there 10^5 test cases.

i found out can compute recurrence relation t_i = 6t_i-1 - t_i-2 + 2, t₀ = 0 , t₁ = 1.

i'm using matrix exponentiation approximately o(log n) performance per test case, it's apparently slow, since there 10^5 test cases. in fact, code slow when constraints (1 ≤ n ≤ 10^6), o(n) preprocessing , o(1) query.

should change approach problem, or should optimize parts of code?

#include <ios> #include <iostream> #include <vector> #define mod 10006699  /* transformation matrix:   0 1 0   t[i]     t[i+1] -1 6 1 * t[i+1] = t[i+2]  0 0 1     2        2 */  std::vector<std::vector<long long int> > multi(std::vector<std::vector<long long int> > a, std::vector<std::vector<long long int> > b) {     std::vector<std::vector<long long int> > c(3, std::vector<long long int>(3));     (int = 0; < 3; i++)     {         (int j = 0; j < 3; j++)         {             (int k = 0; k < 3; k++)             {                 c[i][j] += (a[i][k] * b[k][j]) % mod;                 c[i][j] %= mod;             }         }     }     return c; }  std::vector<std::vector<long long int> > power(std::vector<std::vector<long long int> > vec, long long int p) {     if (p == 1) return vec;     else if (p % 2 == 1) return multi(vec, power(vec, p-1));     else     {         std::vector<std::vector<long long int> > x = power(vec, p/2);         return multi(x, x);     } }  int main() {     std::ios_base::sync_with_stdio(false);     long long int n;     while (std::cin >> n)     {         if (n == 0) break;         else         {             std::vector<std::vector<long long int> > trans;             long long int ans;             trans.resize(3);              trans[0].push_back(0);               trans[0].push_back(1);             trans[0].push_back(0);             trans[1].push_back(-1);             trans[1].push_back(6);             trans[1].push_back(1);             trans[2].push_back(0);             trans[2].push_back(0);             trans[2].push_back(1);              trans = power(trans, n);              ans = (trans[0][1]%mod + (2*trans[0][2])%mod)%mod;              if (ans < 0) ans += mod;              std::cout << ans << std::endl;         }     } } 

note: removed old answer, more useful

it seems unlikely create better asymptotic algorithm o(log n) problem. however, there modifications can performed current code not improve asymptotic time improve performance

below modification of code produces same answer:

#include <ctime> #include <ios> #include <iostream> #include <vector> #define mod 10006699  void power(std::vector<std::vector<long long int> >& vec, long long int p) {     if (p == 1)         return;      else if (p & 1)     {         std::vector<std::vector<long long int> > copy1 = vec;         power(copy1, p-1);          std::vector<std::vector<long long int> > copy2(3, std::vector<long long int>(3));         (int = 0; < 3; i++)             (int j = 0; j < 3; j++)             {                 (int k = 0; k < 3; k++)                     copy2[i][j] += (vec[i][k] * copy1[k][j]) % mod;                 copy2[i][j] %= mod;             }         vec = copy2;          return;     }      else     {         power(vec, p/2);          std::vector<std::vector<long long int> > copy(3, std::vector<long long int>(3));         (int = 0; < 3; i++)             (int j = 0; j < 3; j++)             {                 (int k = 0; k < 3; k++)                     copy[i][j] += (vec[i][k] * vec[k][j]) % mod;                 copy[i][j] %= mod;             }         vec = copy;          return;     } }  int main() {     std::ios_base::sync_with_stdio(false);     long long int n;     while (std::cin >> n)     {         std::clock_t start = std::clock();         if (n == 0) break;          std::vector<std::vector<long long int> > trans;         long long int ans;         trans.resize(3);          trans[0].push_back(0);           trans[0].push_back(1);         trans[0].push_back(0);         trans[1].push_back(-1);         trans[1].push_back(6);         trans[1].push_back(1);         trans[2].push_back(0);         trans[2].push_back(0);         trans[2].push_back(1);          power(trans, n);          ans = (trans[0][1]%mod + (2*trans[0][2])%mod)%mod;         if (ans < 0) ans += mod;         std::cout << "answer: " << ans << std::endl;          std::cout << "time: " << (std::clock() - start) / (double)(clocks_per_sec / 1000) << " ms" << std::endl;     } } 

the differences are:

• a code motion of c[i][j] %= mod; outside k loop
• passing vectors reference
• less function calls

if place same timing code in while loop of main have in code, name file "before.cpp", name file "after.cpp", , run each 10 times in row full optimizations these results:

alexanders-mbp:desktop alexandersimes$ g++ before.cpp -o3 -o before alexanders-mbp:desktop alexandersimes$ ./before  1000000000000000000 answer: 6635296 time: 0.708 ms 1000000000000000000 answer: 6635296 time: 0.542 ms 1000000000000000000 answer: 6635296 time: 0.688 ms 1000000000000000000 answer: 6635296 time: 0.634 ms 1000000000000000000 answer: 6635296 time: 0.626 ms 1000000000000000000 answer: 6635296 time: 0.629 ms 1000000000000000000 answer: 6635296 time: 0.629 ms 1000000000000000000 answer: 6635296 time: 0.629 ms 1000000000000000000 answer: 6635296 time: 0.632 ms 1000000000000000000 answer: 6635296 time: 0.695 ms  alexanders-mbp:desktop alexandersimes$ g++ after.cpp -o3 -o after alexanders-mbp:desktop alexandersimes$ ./after  1000000000000000000 answer: 6635296 time: 0.283 ms 1000000000000000000 answer: 6635296 time: 0.287 ms 1000000000000000000 answer: 6635296 time: 0.27 ms 1000000000000000000 answer: 6635296 time: 0.27 ms 1000000000000000000 answer: 6635296 time: 0.266 ms 1000000000000000000 answer: 6635296 time: 0.265 ms 1000000000000000000 answer: 6635296 time: 0.266 ms 1000000000000000000 answer: 6635296 time: 0.267 ms 1000000000000000000 answer: 6635296 time: 0.21 ms 1000000000000000000 answer: 6635296 time: 0.208 ms