程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5047 Sawtooth

hdu 5047 Sawtooth

編輯:C++入門知識

hdu 5047 Sawtooth


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
2
1
2

Sample Output
Case #1: 2
Case #2: 19

Source 2014 ACM/ICPC Asia Regional Shanghai Online


題解及代碼:

推導公式很簡單:首先通過看圖,我們可以知道,任意兩個M都能相交出現16個交點,然後對M進行標號1--n,總的交點數就是∑16*i (1=

然後根據:邊數+點數+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 
#include 
#include 
#include 
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\n",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\n",l_m,r_m);
        else printf("%I64d\n",r_m);
    }
    return 0;
}






  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved