列表

详情


NC24897. NB群友

描述

CC是著名的算法竞赛选手,他不仅人长得帅,而且技术了得,自然而然就有了许多粉丝。

为了能帮助粉丝们提高竞技水平,CC建立了一个粉丝群,每天CC都会在粉丝群里和群友深入交流黑科技。然而,有些群友老是不努力训练,成天想着复读,比如当CC在群里面发了个整数0,那紧接着就会有群友发整数1,然后又会有群友发整数2……这引起了CC的不满,于是CC决定踢掉一些群友。

CC的粉丝群人数为无穷大。当CC发出整数0后,其他群友就会跟着轮流发整数1, 2, 3, 4, ...,依此类推。需要注意的是,每个群友都会恰好发一次整数,每个群友发的整数两两不同。CC认为,在不考虑前导零的情况下,如果某个群友发的整数在十进制表示下的各位数字不含0及1,那么这个群友就是NB的,否则就是不NB的。例如,群友A发的整数是3482,该数的各位数字分别为3、4、8、2,其中不含0、1,因此群友A是NB的;另一方面,群友B发的整数402,而该数的十位数字是0,因此群友B是不NB的。

现在CC决定,踢掉所有不NB的群友。于是经过一番奥妙重重的踢人操作后,粉丝群里只剩下NB群友。然而,CC觉得剩下的这些NB群友还是too naive,因此他打算邀请一些NB群友参加线下训练营(来现场教做人)。具体来说,CC会给出两个正整数L,R,然后他会邀请发出的整数的各位数字之积在区间[L,R]内的NB群友。

举例来说,假如CC给出的区间为L = 50, R = 300,那么发了567的群友会被邀请线下参赛,因为5×6×7=210;同理,发了255的群友也会被邀请,因为2×5×5=50。但是,发了328的群友则不会收到邀请,因为3×2×8=48∉[50,300]。

输入描述

第一行是一个整数T (1≤T≤50),表示数据组数。
接下来T行,每行两个整数,表示一组询问。

输出描述

输出共T行。对于每个询问,输出一行一个整数ans,表示CC邀请参加线下训练营的NB群友人数模的结果。

示例1

输入:

4
3 6
4 9
2147483648 4294967295
5 5

输出:

7
13
793516016
1

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 266ms, 内存消耗: 5488K, 提交时间: 2019-04-16 20:24:52

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll>mm;
const int mod=1e9+7;
ll dfs(ll x){
	if(x==1||x==0)
		return 0;
	if(mm[x])
		return mm[x];
	ll ans=0;
	for(int i=2;i<=9;i++)
		if(x>=i)
			ans+=dfs(x/i)+1;
	return mm[x]=ans;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		ll l,r;
		cin>>l>>r;
		cout<<(dfs(r)-dfs(l-1)+mod)%mod<<endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 234ms, 内存消耗: 5536K, 提交时间: 2020-02-26 17:20:19

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e9+7;
map<ll,ll>mp;
ll dfs(ll x)
{
	if(mp[x]||x==1)
	{
		return mp[x];
	}
	ll ans=0;
	for(int i=2;i<=min(x,(ll)9);i++)
	{
		ans=((ans+dfs(x/i))+1)%N;
	}
	mp[x]=ans;
	return ans;
}
int main()
{
	ll l,r,t;
	cin>>t;
	while(t--)
	{
		cin>>r>>l;
		cout<<(dfs(l)-dfs(r-1)+N)%N<<endl;
	}
}

上一题