#25722: 請問MLE的辦法


jiaaaapa@gmail.com (我不會啦)

School : No School
ID : 156350
IP address : [36.238.157.98]
Last Login :
2021-06-17 01:42:46
a010. 因數分解 | From: [36.238.157.98] | Post Date : 2021-06-17 02:13

大概寫得很爛,抱歉......

只剩#2過不了,求指教。

 

import java.io.BufferedReader;

import java.io.InputStreamReader;

 

public class bbbb {

 

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

int a, g, c=-1;

String s="", n;

bbbb() throws Exception

{

a=Integer.parseInt(br.readLine());

g=a;

int[] t=new int[a];

for(int i=2;i<=a;i++)

{

if(a%i==0)

{

a/=i;

s+=i+" ";

i--;

}

}

n=s.split(" ")[0];

t[Integer.parseInt(n)-1]=1;

for(int i=1;i<s.split(" ").length;i++)

{

if(s.split(" ")[i].equals(n))

t[Integer.parseInt(n)-1]+=1;

else

{

n=s.split(" ")[i];

t[Integer.parseInt(n)-1]=1;

}

}

for(int i=0;i<g;i++)

{

if(t[i]>0)

c++;

}

for(int i=0;i<g;i++)

{

if(t[i]==1)

{

System.out.print(i+1);

if(c!=0)

{

System.out.print(" * ");

c--;

}

}

else if(t[i]>1)

{

System.out.print((i+1)+"^"+t[i]);

if(c!=0)

{

System.out.print(" * ");

c--;

}

}

}

}

 

public static void main(String[] args) throws Exception {

new bbbb();

}

 

}

 

 
#25729: Re:請問MLE的辦法


jam930725@gmail.com (浮沉沉沉沉沉沉沉沉)

School : 國立臺中科技大學
ID : 124762
IP address : [123.110.34.107]
Last Login :
2021-08-02 10:47:34
a010. 因數分解 | From: [123.110.34.107] | Post Date : 2021-06-17 16:59

問題出在 int[] t=new int[a]; 這行,

最大的輸入為 10**8

也就是陣列t最大的大小為 4 bytes + 4*(10**8) bytes

約莫為 380 MB , 已經超過題目限定的64MB

--------------分隔線----------------

其實這題可以邊做邊輸出。

以 200 做例子

從2開始檢查,發現可以除3次

然後檢查 是否為第一個因數,發現是 因此輸出 2^3 

接著檢查到5,發現可以除2次

然後檢查 是否為第一個因數,發現否 因此輸出 * 5^2

此時target==1 離開迴圈

 

以17作為例子

從2開始檢查,一直檢查到 Math.ceil(Math.sqrt(17)),都沒有發現因數

因此輸出 17

 

以 999997 為例

在 Math.sqrt(999997) 內,發現因數757

為第一個因數 因此輸出 757

一直檢查到 Math.sqrt(999997) 離開迴圈

此時輸入尚未被除盡,且前面已經輸出過其他因數,因此輸出 * 1321

 

如此 就不需要另開一個陣列去記數。

另外加速的方法,可以直接把1~1000內的質數建表(共168個),就可以省去判斷非質數的數的時間。

在for迴圈開始前,可以先計算sqrt(input),就不用迴圈每執行一次就要計算一次

--------------分隔線----------------

程式碼的部分,直接寫在main裡面就可以了,不需要另外寫一個建構元再去呼叫,看起來很奇怪

還有如果是因為使用了BufferedReader,而需要做例外處理,通常會用IOException (需要先import java.io.IOException 或是直接 import java.io.*)

 
ZeroJudge Forum