NC24897. NB群友
描述
输入描述
第一行是一个整数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; } }