P9651 题解

Jasoncwx · 2023-09-17 13:40:32 · 题解

题目思路

不难发现，只要 [l,r] 中出现至少一个整十数，也就是存在至少一个 l\le i\le r，使得 i\bmod10=0，这样 f(i) 的最终结果肯定为 0，导致了 \prod_{i=l}^r f(i) 也会为 0。

那我们在什么情况下输出 0 呢？

可以证明，在 r-l+1\ge10 的情况下，至少会出现一个整十数。因为要使得一个区间内没有整十数，这个区间内不能多于 9 个数。

顾名思义，"整十数"就是每隔 10 个整数会出现一次，所以我们要避免这种情况就只能不多于 9 个数了。

所以在 r-l+1\ge10 时直接输出 0，其它情况直接暴力枚举即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long f(int n){
    string s=to_string(n);
    long long sum=1;
    for(int i=0;i<s.size();i++)sum*=s[i]-'0';
    return sum;
}//计算 f(n)
int main(){
    int t;
    cin>>t;
    while(t--){
        int l,r;cin>>l>>r;
        if(r-l+1>=10)puts("0");//区间中出现整十数
        else{
            long long sum=1;
            for(int i=l;i<=r;i++){
                sum=(sum*f(i))%mod;//答案
            }
            cout<<sum<<endl;
        }
    }
}