【解题报告】洛谷P1062 数列&&CF1594B

题目链接

https://www.luogu.com.cn/problem/P1062

https://www.luogu.com.cn/problem/CF1594B

思路

u1s1，实际上CF的题目正好是这个普及组题目的加强版

但是两个都很简单

我们把第 nn 项中 nn 用二进制展开

发现了每个要假的幂都是对应的一个从右向左数的1的位置，这样就很好做了

CF代码，PJ代码改一改就随便过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int long long
using namespace std;
const int mod=1e9+7;
int T; 
signed main()
{
	cin>>T;
	while(T--)
	{
		int n,k;
		cin>>n>>k;
		int res=0;
		int a=1;
		while(k)
		{
			if(k&1)
			res=(res%mod+a%mod)%mod;
			a=a%mod*n%mod;
			k>>=1;
		}
		cout<<res<<'\n';
	}
	return 0;
}