codecstasy

1594B

Nov 28th, 2021
466
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long m = 1e9 + 7;
  5.  
  6. long long power(long long a, long long b){
  7.     long long s = 1;
  8.     for(long long i = 1; i <= b; i++){
  9.         s *= (a % m) % m;
  10.     }
  11.     return s;
  12. }
  13.  
  14. void solve() {
  15.     long long int n,k,pos=0;
  16.     long long sum=0;
  17.     vector <long long> v;
  18.     cin >> n >> k;
  19.     while(k) {
  20.         if(k & 1) v.push_back(pos);
  21.         k >>= 1;
  22.         pos++;
  23.     }
  24.     //for(int i=0 ; i<v.size() ; i++) cout << v[i] << " ";
  25.     for(int i=0 ; i<v.size() ; i++) {
  26.         sum += (power(n,v[i]) % (long long)(1e9+7));
  27.     }
  28.     cout << sum << endl;
  29. }
  30.  
  31. int main() {
  32.     int t;
  33.     cin >> t;
  34.     while(t--) {
  35.         solve();
  36.     }
  37.     //cout << power(4,3);
  38. }
RAW Paste Data