完全平方數(shù)

發(fā)布時(shí)間: 2017年6月24日 17:01?? 最后更新: 2017年7月3日 09:27?? 時(shí)間限制: 1000ms?? 內(nèi)存限制: 128M

描述

給定正整數(shù)b，求最大的整數(shù)a，使a(a+b)是完全平方數(shù)。

輸入

多組測(cè)試數(shù)據(jù)（不超過(guò)10000組）。
每組數(shù)據(jù)一個(gè)正整數(shù)b,b≤109。

輸出

對(duì)每組數(shù)據(jù)輸出一行一個(gè)整數(shù)a，表示答案。

樣例輸入1 1 3 5 樣例輸出1 0 1 4 這道題目，代碼很短，重點(diǎn)在思維上面。

我們這樣考慮，設(shè)a = kt^2，且k是素?cái)?shù)

那么a(a+b) = kt^2(kt^2 + b)是完全平方數(shù)

相當(dāng)于k(kt^2 + b)是完全平方數(shù)

由于完全平方數(shù)中包含素?cái)?shù)k，則k的次數(shù)必為偶數(shù)次

那么k^2 | k(kt^2 + b)

也就是說(shuō)k | b

設(shè)b = ke

那么等價(jià)轉(zhuǎn)化到k^2(t^2+e)是完全平方數(shù)

相當(dāng)于t^2 + e是完全平方數(shù)

考慮e的取值

e = 2t + 1的時(shí)候，t^2 + e是完全平方數(shù)

e = 4t + 4的時(shí)候，t^2 + e是完全平方數(shù)

要使得a = kt^2越大，直覺(jué)上認(rèn)為t一定要越大

所以說(shuō)，如果n為奇數(shù)的情況下t = (e-1)/2 = (n-1)/2; k = 1;這樣最好

如果n為偶數(shù)的話(huà)，如果n/2為奇數(shù)的話(huà)，那么k = 2;t = (n/2-1)/2;這樣最好

而如果n為偶數(shù)，n/2仍然為偶數(shù)的話(huà)，那么k = 1;e = (n-4)/4 ?這樣最好

#include <iostream> #include <cstdio> #include <cmath> using namespace std; typedef long long LL; const int MAX = 1e9; LL n; int main(){while(~scanf("%lld",&n)){LL ans;if(n % 2){//奇數(shù)LL t = (n-1)/2;ans = t*t;}else if(n%4 == 0){LL t = (n-4)/4;ans = t*t;}else{LL t = (n/2-1)/2;ans = t*t*2; }printf("%lld\n",ans); }return 0; }

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的2017西安交大ACM小学期数论 [完全平方数]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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