[ACM] POJ 1183 解题报告

94 Replies

a = (b*c-1)/(b+c) 令m = b+c => c = m-b
推得 m = – (b^2 + 1)/(a – b)
做一下多项式除法后 m = (b – a) + (a^2 + 1)/(b – a) + 2a
所以令k=b – a (由arctan()的函数图像知k>0)

=> m = k + (a^2 + 1)/k + 2a
根据函数图像知道 (0 , 根号(a^2 + 1)]内递减, [根号(a^2 + 1), +∞)内递增, 所以我们需要求两个区间上最靠近根号(a^2 + 1)的使m为整数的k
设 i>=根号(a^2 + 1) 则对于此情况下要求的mi = i + (a^2 + 1)/i + 2a 有 j = (a^2 + 1)/i 使
mi = (a^2 + 1)/j + j + 2a
而 j<=根号(a^2 + 1) 所以右边区间满足情况的i在左边都能找到对应的j, 所以只要搜索左边就行了

k=n..1
找出最先使 (a*a+1)%k==0的k即可
[cpp]
#include <stdio.h>
int main() {
int a;
scanf("%d",&a);
int k=a;
long long foo=(long long)a*a+1;
while(foo%k)
k–;
printf("%d\n",k+foo/k+2*a);
return 0;
}
[/cpp]

94 thoughts on “[ACM] POJ 1183 解题报告”

Leave a Reply

Your email address will not be published. Required fields are marked *