hdu 5047 Sawtooth
來源：程序員人生 發布時間：2014-09-29 21:26:28 閱讀次數：3046次
Sawtooth
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 258 Accepted Submission(s): 78
Problem Description
Think about a plane:
● One straight line can divide a plane into two regions.
● Two lines can divide a plane into at most four regions.
● Three lines can divide a plane into at most seven regions.
● And so on...
Now we have some figure constructed with two parallel rays in the same direction, joined by two straight segments. It looks like a character “M”. You are given N such “M”s. What is the maximum number of regions that these “M”s can divide a plane ?
Input
The first line of the input is T (1 ≤ T ≤ 100000), which stands for the number of test cases you need to solve.
Each case contains one single non-negative integer, indicating number of “M”s. (0 ≤ N ≤ 1012)
Output
For each test case, print a line “Case #t: ”(without quotes, t means the index of the test case) at the beginning. Then an integer that is the maximum number of regions N the “M” figures can divide.
Sample Input
Sample Output
Source
2014 ACM/ICPC Asia Regional Shanghai Online
題解及代碼：
推導公式很簡單：首先通過看圖，我們可以知道，任意兩個M都能相交出現16個交點，然后對M進行標號1--n，總的交點數就是∑16*i (1=<i<n)，
然后根據：邊數+點數+1=分成的區域數，可以算出公式是：8*n^2-7*n+1。因為數比較大，所以會想到用java，結果kuangbin大神卡的很緊Orz....
那就用c++的大數模版來吧，通過觀察我們發現：上述公式可以轉換一下成n*(8*n-7)+1，這里8*n可以用位運算來算，我們讓m=8*n-7，m最大也到
不了10^13，而n最大是10^12，這樣我們可以利用大數的思想，將m分成兩部分，分別與n進行相乘，最后簡單處理一下輸出就行了。
Time：187ms
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=1000000;
int main()
{
ll n,m,l_m,r_m;
int cas;
scanf("%d",&cas);
for(int ca=1; ca<=cas; ca++)
{
scanf("%I64d",&n);
//printf("%I64d
",8*n*n-7*n+1);
m=(n<<3)-7;
l_m=m/mod;
r_m=m%mod;
l_m*=n;
r_m=r_m*n+1;
l_m=l_m+r_m/mod;
r_m%=mod;
printf("Case #%d: ",ca);
if(l_m) printf("%I64d%06I64d
",l_m,r_m);
else printf("%I64d
",r_m);
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
