CodeForces - 233B Non-square Equation 數學+一進制二次方程+配方

題意

給你一個一進制二次方程 x2 + s(x)⋅x − n = 0 x 2   +   s ( x ) · x   −   n   =   0 ， s(x) s ( x ) 表示，x的各數位之和，

例如：

s(11)=1+1=2 s ( 11 ) = 1 + 1 = 2

s(123)=1+2+3=6 s ( 123 ) = 1 + 2 + 3 = 6

s(256)=2+5+6=13 s ( 256 ) = 2 + 5 + 6 = 13

接下來，給你一個正整數n，讓你求正整數 x！存在輸出x，不存在就輸出-1；

真心數學題。

分析：

x2 + s(x)⋅x − n = 0(0) (0) x 2   +   s ( x ) · x   −   n   =   0

x2+s(x)⋅x−n+s(x)24=s(x)24(1) (1) x 2 + s ( x ) · x − n + s ( x ) 2 4 = s ( x ) 2 4

(x+s(x)2)2=s(x)24+n(2) (2) ( x + s ( x ) 2 ) 2 = s ( x ) 2 4 + n

x+s(x)2=s(x)24+n−−−−−−−√(3) (3) x + s ( x ) 2 = s ( x ) 2 4 + n

x=s(x)24+n−−−−−−−√−s(x)2(4) (4) x = s ( x ) 2 4 + n − s ( x ) 2

高中學習過的一進制二次方程的配方~

接下來，分析資料， 1 ≤ n ≤ 1018 1   ≤   n   ≤   10 18

x2 + s(x)⋅x − n = 0(0) (0) x 2   +   s ( x ) · x   −   n   =   0

x2 + s(x)⋅x = n (5) (5) x 2   +   s ( x ) · x   =   n  

方程0 —>>方程5 不解釋；

由方程5得： x2 x 2 與 n n 數量級相同

即：1 ≤ x2≤ 10181 ≤ x2≤ 1018

即： 1 ≤ x≤ 10181/2=109 1   ≤   x ≤   10 18 1 / 2 = 10 9

即：x的最大值為999999999(9個9)

那麼： s(x) s ( x ) 的最大值為 9∗9=81 9 ∗ 9 = 81 ，最小值為 1 1

綜上：結合方程4 ，n為給定值，s(x)s(x)周遊區間 [1,81] [ 1 , 81 ] ,隻有x為未知量，分别求解出81個x，帶入原方程0中，判斷下就ok了！

重新上了一遍高中的數學課。。。。

代碼：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iomanip>
#define maxn 100005
#define ll long long
#define debug cout<<"***********"<<endl;
using namespace std;

int sumDigit(ll n){
    int sum = ;
    while(n){
        sum += n%;
        n /= ;
    }
    return sum;
}

int main(){
    ll n;cin>>n;
    bool flag = false;
    ll sumX = ;
    for(int i = ; i < ; i++){
        sumX = sqrt( (double)i*i/ + n) - i/;
        if(sumX * sumX + sumDigit(sumX)*sumX - n == ){
            flag = true;
            break;
        }
    }
    if(flag){
        cout<<sumX<<endl;
    }
    else{
        cout<<"-1"<<endl;
    }
    return ;
}
           

加油少年！