#10351: TLE (逾時)


davidrfdg (unknown)

學校 : 不指定學校
編號 : 53162
來源 : [125.227.255.80]
最後登入時間 :
2015-10-27 13:26:31
d639. 企鵝村三兄弟penguin -- jack1 | From: [220.137.19.184] | 發表日期 : 2015-10-13 21:30

 import java.util.Scanner;

 

public class D639 {

 

public static void main(String[] args) {

double a = 1., b = 1., c = 1., sum = 0.;

Scanner input = new Scanner(System.in);

while (input.hasNextInt()) {

int n = input.nextInt();

 

if (n <= 3) {

System.out.println(1);

} else {

for (int i = 4; i <= n; i++) {

sum = a + b + c;

a = b;

b = c;

c = sum;

sum%=10007;    //本來沒這行,這行是後來才加的,還是過不了

}

System.out.print((int)sum);

}

sum = 0;

a = 1;

b = 1;

c = 1;

}

input.close();

}

}

 

請問,自己跑沒問題,可是交卷後卻愈時,要怎麼解決?

 
#10828: Re:TLE (逾時)


p3a_owhj (阿普二信)

學校 : 不指定學校
編號 : 39897
來源 : [36.227.79.178]
最後登入時間 :
2024-06-04 22:09:36
d639. 企鵝村三兄弟penguin -- jack1 | From: [203.77.43.132] | 發表日期 : 2016-04-01 22:41

n的值超過10^9不可能迴圈跑10億次不逾時的

我看過一篇文章求費氏數列第 n 個,也是 n 的值超過10^9的

該文章介紹的解法是

2列1欄的向量<f(n+2),f(n+1)> = 2x2陣列A 乘上  2x1的向量<f(n+1),f(n)> = .... = An 乘上  2列1欄的向量<f(2),f(1)>即< 1 , 1 >

其中 A 陣列為 1 1

                    1 0

所以重點是求 A陣列的 n 次方,當然是不跑 n 次迴圈,而是用二進位的方式

我又看過一篇介紹求數字 Xn 的二進位法,好像類似以下方式,

假設 n = 11 轉成二進位1 0 1 1 則 x11可以改為 ( ( (1*x))*x )*x  註: 由左至右遇1時*x

若數字太大會取模,例如 mod = 10..07

以下是以二進位法求Xn取mod後的示意程式碼,例如求 12345的2345678次方後被100007除後的餘數?

int binpow(int x , int n , int mod)

{

假設已將 n 轉為 b[0]~b[k-1]的二進位

  p=1;

  for(i=0; i<k; ++k)
  {
      p = p*p%mod;
      if(b[i]) p*x%mod;
  }

  return p;

}

以上只是憑印象給的意見,還沒確認,若有錯誤請見諒!

 
 
#10829: Re:TLE (逾時)


p3a_owhj (阿普二信)

學校 : 不指定學校
編號 : 39897
來源 : [36.227.79.178]
最後登入時間 :
2024-06-04 22:09:36
d639. 企鵝村三兄弟penguin -- jack1 | From: [203.77.43.132] | 發表日期 : 2016-04-01 22:47

剛貼上才發現有一篇 Big Mod 的解題心得可以參考

http://zerojudge.tw/ShowThread?postid=10758&reply=0

 
 
ZeroJudge Forum