BZOJ 4292: [PA2015]Równanie – [暴力与乱搞]


题目传送门(BZOJ)
>原文链接<

题解 :

首先这个东西肯定满足前缀相减性质, 也就是问题从求a\sim b变成求1\sim n

并且, 在10^{18}范围内的最大一个ff(999999999999999999)=81\times 18 = 1458

我们可以枚举一个f值, 然后对于这个f进行验证即可

\because k\times f(n)=n

\therefore f(k\times f(n))=f(n), 也就是我们枚举出来的这个值

如果满足, 直接累加答案即可

代码 :

#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
ll k, a, b;
int calc(ll n) {
    int ans = 0;
    while(n) {
        int k = n%10;
        ans += k*k;
        n /= 10;
    }
    return ans;
}
int solve(ll n) {
    int ans = 0;
    for(int i = 1; i <= 1458; i ++ ) {
        if(i*k > n) break;
        if(calc(i*k) == i) ans ++;
    }
    return ans;
}
int main() {
    scanf("%lld%lld%lld", &k, &a, &b);
    printf("%d\n", solve(b)-solve(a-1));
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注