Codeforces Round #747 (Div. 2) B. Special Numbers

用快速幂的思路做,通过k的二进制位数表示答案中加不加相应的位数.复杂度O(logn)

#include
using namespace std;

#define LL long long
const int mod=1e9+7;

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,k,i;
		LL ans=0;//存答案
		LL flag=1;//存要加进去的数
		
		cin>>n>>k;
		for(i=0;k>0;i++,k=k>>1)//k通过右移来减小和判断位数
		{
			if(k&1)//如果当前二进制位上为1就加
			ans+=flag%mod;
			flag=flag*n%mod;
			ans%=mod;//任何时候都要取个模
		}
		cout<