- 总时间限制: 1000ms 内存限制: 65536kB
- 描述
-
我家住在一条短胡同里，这条胡同的门牌号从1开始顺序编号。
若所有的门牌号之和减去我家门牌号的两倍，恰好等于n，求我家的门牌号及总共有多少家。
数据保证有唯一解。
- 输入
- 一个正整数n。n < 100000。
- 输出
- 一行，包含两个正整数，分别是我家的门牌号及总共有多少家，中间用单个空格隔开。
- 样例输入
-
100
- 样例输出
-
10 15
问题分析
本题的用穷举法求解。
假设总共有k家，我家门牌号为x，那么k(k+1)/2 -2x=n，得k(k+1)-2n=4x>=4（因为x>=1）。
推导得：(k+1)(k+1) > k(k+1)>=4+2n，最后得：k>sqrt(4+2n)-1。
程序说明
程序中，尽量减少穷举的数量。
代码一：
1 #include <stdio.h> 2 int main(int argc, char *argv[]) 3 { 4 int k,n,x,sum=1; 5 6 scanf("%d",&n); 7 //n=100; 8 for(k=2;k<=n;k++) 9 { 10 sum=sum+k; 11 if(sum>n&&(sum-n)%2==0) {x=(sum-n)/2;break;} 12 } 13 printf("%d %d\n",x,k); 14 return 0; 15 }
代码二：
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 int main() 5 { 6 int n, mink, x,k; 7 8 cin >> n; 9 10 mink = sqrt(4 + 2 * n) - 1; 11 12 for(k=mink+1; ;k++) 13 { 14 if((k * k + k- 2 * n) % 4 == 0) 15 { 16 x = (k * k + k - 2 * n) / 4; 17 if(x <= 0) 18 continue; 19 cout << x << " " << k<< endl; 20 break; 21 } 22 } 23 24 return 0; 25 }
