http://codeforces.com/problemset/problem/233/B

題意：

x²?+?s(x)·x?-?n?=?0,? 給出n的值，求x的值，這里s(x)表示x各位數(shù)字的和。

思路：

才開始我錯(cuò)誤的認(rèn)為x^2 + s(x)*x 是一個(gè)單調(diào)遞增函數(shù)，于是分析x<10^9然后二分枚舉log(10^9)即可，結(jié)果寫完后樣例都沒過。原來這個(gè)函數(shù)不是單調(diào)函數(shù)10 = 110 9 = 162 所以非單調(diào)。

一時(shí)蒙了。還是做的數(shù)學(xué)題目比較少吧，思路還不夠開闊。這里我能夠得到x<10^9那么s(x)< 10*9 = 90 我們只要枚舉s(x) 然后得到一個(gè)普通的一元二次方程，a*x^2 + b*x + c = 0然后根據(jù)公式

x = (-b +or - sqrt(b^2 -4*a*c )/2這里我們求的都是整數(shù)解，所以在計(jì)算的時(shí)候我們要保證得到的解是整數(shù)才可。

?

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a,b) (a) > (b)? (b):(a) #define Max(a,b) (a) > (b)? (a):(b)#define ll long long #define inf 0x7f7f7f7f #define MOD 1073741824 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 1000007 #define N 100007 using namespace std; //freopen("data.in","r",stdin); ll sum(ll x){ll res = 0;while (x != 0){res += x%10;x /= 10;}return res; } int main(){int i;ll n;cin>>n;ll res = -1;for (i = 1; i <= 90; ++i){ll root = i*i + 4*n;ll tmp = sqrt(root);if (tmp * tmp == root){//保證整數(shù)解tmp = (tmp - i);if (tmp%2 == 0 && sum(tmp/2) == (ll)i){//枚舉b得到x然后檢查x是否滿足條件if (res == -1) res = tmp/2;elseres = min(res,tmp/2);}}}cout<<res<<endl;return 0; }

?

這里還有一個(gè)解法，很多人都是這么過的，又是一個(gè)經(jīng)典的騙數(shù)據(jù)。

因?yàn)閤=<sqrt(n)那么解一定[1,sqrt(n)]里面，我們只要枚舉sqrt(n)坐標(biāo)100個(gè)點(diǎn)即可把數(shù)據(jù)騙過。

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a,b) (a) > (b)? (b):(a) #define Max(a,b) (a) > (b)? (a):(b)#define ll __int64 #define inf 0x7f7f7f7f #define MOD 1073741824 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 1000007 #define N 100007 using namespace std; //freopen("data.in","r",stdin); ll f(ll a){ll tmp = a;ll sum = 0;while (tmp != 0){sum += tmp%10;tmp /= 10;}return (a*a + a*sum); } int main(){ll n;int i;while (cin>>n){ll tp = sqrt(n);for (i = max(tp - 100, 1ll); i <= tp; ++i){if (f(i) == n){printf("%d\n",i);break;}}if (i > tp) printf("-1\n");}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/E-star/archive/2012/10/24/2736749.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #144 (Div. 2) B. Non-square Equation 数学解一元二次方程+分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。