题解 AT2038 【桁和 / Digit Sum】

henry_y · 2018-09-17 15:51:50 · 题解

推一下博客

总结：数学题

被数学题虐爆...研究了好久的题解才明白这题...

题意：给一个函数f(b,n)可以求出n在b进制下各位数的和，设f(b,n)=s，现在已知n,s，求b

我们可以分成两种情况来讨论

当b<=\sqrt{n}时，我们可以直接枚举b，然后套用题目的公式来计算

当b>\sqrt{n}时，我们可以寻找一下规律：

设n在b进制下的高位为p低位为q（因为b>\sqrt{n},所以这里的n在b进制下一定是两位数）

这时的n=pb+q ， s=p+q

所以n-s=(b-1)p

即b=\frac{n-s}{p}+1

因为b是整数，所以枚举n-s的所有因数p就可以了，不过枚举之后要更新答案的时候记得再套一遍f(b,n)来检查一下，因为算出来的b可能会出现某些奇奇怪怪的东西（亲测...）

复杂度是O(\sqrt{n})的

#include <bits/stdc++.h>

using namespace std ;

#define inf 0x3f3f3f3f
#define ll long long

ll n , s ;

ll f( ll b , ll n ) {
    return n < b ? n : f( b , n / b ) + n % b ;
}

int main() {
    scanf( "%lld%lld" , &n , &s ) ;
    if( s > n ) return puts( "-1" ) , 0 ;
    if( s == n ) return printf( "%lld\n" , n + 1 ) , 0 ;
    ll m = sqrt( n ) + 1 ;
    for( ll i = 2 ; i <= m ; i ++ ) {
        if( f( i , n ) == s ) 
            return printf( "%lld" , i ) , 0 ;
    }
    ll ans = 1e11 ; n -= s ;
    for( ll i = 1 ; i * i <= n ; i ++ ) {
        if( n % i == 0 ) {
            ll b = n / i + 1;
            if( f ( b , n + s ) ==  s ) ans = min ( ans , b ) ;
        }
    }
    printf( "%lld\n" , ans != 1e11 ? ans : -1 ) ;
    return 0 ;
}