b949: 3rd CPSC Problem 3－－「障」量土地

b949: 3rd CPSC Problem 3－－「障」量土地

題目連結:b949: 3rd CPSC Problem 3－－「障」量土地

題意:

給你一個正整數M(M<2^31),求M*M*25

解法:

C++:

測資很多,需優化I/O

最大測資是(2^31-1)^2*25

已經大於unsigned long long int 的 2^64-1

直覺用大數運算來做

但是TLE了(其實原本可以過的(0.6S,324KB),系統升級後變慢,重新測就TLE了)

time(重測前/後): 0.6s/TLE(2s)

memory used(重測前/後): 324KB/TLE

code:

#include<iostream>


#include<iomanip>


using namespace std;


int main(){


ios::sync_with_stdio(false);


cin.tie(0);


short int a,i,b,d;


long long int n,m=2,v,s,g;


while(cin>>g){


n=g*5;


long long int x[3]={0};


v=0;


s=1;


x[0]=1;


for(a=1;a<=m;a++){


for(i=0;i<s;i++){


x[i]=x[i]*n+v;


v=x[i]/1000000000;


x[i]=x[i]%1000000000;


if(v!=0&&i+1==s)


s++;


}


}


for(b=s-1;b>=0;b--){


if(b!=s-1) cout<<setfill('0')<<setw(9)<<x[b];


else cout<<x[b];


}


cout<<'\n';


}


}

既然大數運算會TLE,那就換個角度思考

有沒有辦法不用大數運算呢?

這題的要我們求的是M*M*25

大家都知道乘以25的心算方式吧

若此數能被4整除,可以先除4然後在數字後面補兩個零就是答案

若不能,答案是在除以4的商後補上此數除以4的餘數乘以25

這樣計算,過程中出現最大的數是M*M,會小於 long long int 的2^63-1

那就用心算方式來解吧

還有,由於4是2的乘冪,所以可以用位元運算來加快速度

以下是兩種一樣算法但不同風格的程式碼

(1)

time(重測前/後): 0.5s/1.5s

memory used: 364KB

code:

#include <iostream>


using namespace std;


int main(int argc, char** argv) {


ios::sync_with_stdio(0);


cin.tie(0);


long long int a,b;


while(cin>>a){


 b=a*a;


 if(b==1)cout<<"25"<<'\n';


 else if(b%4==0)cout<<(b>>2)<<"00"<<'\n';


    else if(b%4==1)cout<<(b>>2)<<"25"<<'\n';


    else if(b%4==2)cout<<(b>>2)<<"50"<<'\n';


    else cout<<(b>>2)<<"75"<<'\n';


}


return 0;


}

(2)

time(重測前/後): 0.5s/1.5s

memory used: 360KB

code:

1. #include <iostream>
2. using namespace std;
3. int main(int argc, char** argv) {
4. ios::sync_with_stdio(0);
5. cin.tie(0);
6. register long long int a,b;
7. while(cin>>a){
8. b=a*a;
9. if(b==1)cout<<"25"<<'\n';
10. else if(b%4==0)cout<<(b>>2)<<"00"<<'\n';
11. else cout<<(b>>2)<<(b%4)*25<<'\n';
12. }
13. return 0;
14. }

如果這樣還不夠快

那就只能再優化I/O了

什麼!!! 還有比優化過的 cin / cout 更快的東西!!!

有的,可以參考這篇: Analysis of Various I/O Methods for Large Datasets in C++

利用 getchar / putchar:

time(重測後): 1.1s

memory used: 64KB

code:

#include<ios>


inline long long int read(){


register long long int a=0;


register char c='0';


while(c>='0'&&c<='9'){


a=(a<<3)+(a<<1)+c-'0';


c=getchar();


}


return a;


}


inline void write(register long long int d){


if(d==0){


putchar(48);


return;


}


register int len=0;


register char n[20];


while(d>0){


n[len]=d%10+48;


len++;


d/=10;


}


for(int i=len-1;i>=0;i--) putchar(n[i]);


}


int main(){


register long long int a,b;


while(a=read()){


b=a*a;


if(b==1)puts("25");


else if(b%4==0)write(b>>2),puts("00");


else write(b>>2),write(b%4*25),putchar('\n');


}


}

還有辦法再更快嗎?
我們可以再去分析這題的數字
正整數M(M<2^31),求M*M*25也就是(M*M/4)*100
M*M是完全平方數,所以我們可以觀察一下完全平方數的性質:

當M為偶數時:
令M=2x(x為自然數)
M^2
=(2x)^2
=4x^2
=4(x^2)-->可被4整除

當M為奇數時:
令M=2x-1(x為自然數)
M^2
=(2x-1)^2
=4x^2-4x+1
=(4x^2-4x)+1
=4(x^2-x)+1-->被4除餘數為1

M為奇數時,M*M被4除的餘數為1
M為偶數時,M*M被4除的餘數為0
也就是說M被2除的餘數等於M*M被4除的餘數
所以我們把問題簡化為判斷M的奇偶並給出相對應的輸出
判斷M的奇偶可以用位元運算實現,會更快一點

time(重測後): 1s

memory used: 76KB
code:

1. #include<cstdio>
2. using namespace std;
3. int main(){
4. register long long int a;
5. while(scanf("%lld",&a)!=EOF){
6. if(a!=1)printf("%lld",(a*a>>2));
7. if(a&1)puts("25");
8. else puts("00");
9. }
10. return 0;
11. }

還可以更快喔
可以使用 getchar_unlocked(),putchar_unlocked()
這兩個東西是競賽選手用的,快到跟黑科技沒兩樣
還可以加上 #pragma 加速運算過程
最後的速度跟怪物一樣...

time(重測後): 0.4s

memory used: 56KB
code:

1. #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
2. #include<ios>
3. inline long long int read(){
4. register long long int a=0;
5. register char c='0';
6. while(c>='0'&&c<='9'){
7. a=(a<<3)+(a<<1)+c-'0';
8. c=getchar_unlocked();
9. }
10. return a;
11. }
12. inline void write(register long long int d){
13. if(d==0){
14. putchar_unlocked(48);
15. return;
16. }
17. register int len=0;
18. char n[20];
19. while(d>0){
20. n[len]=d%10+48;
21. len++;
22. d/=10;
23. }
24. for(int i=len-1;i>=0;i--) putchar_unlocked(n[i]);
25. }
26. int main(){
27. register long long int a;
28. while(a=read()){
29. if(a!=1)write(a*a>>2);
30. if(a&1)puts("25");
31. else puts("00");
32. }
33. }

最後,我們再把getchar_unlocked()換成fread_unlocked()
並加入一些黑科技,把速度再提升

time(重測後): 0.2s

memory used: 1.1MB
code:

1. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
2. #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
3. #pragma comment(linker, "/stack:200000000")
4. #include<ios>
5. char buf[1<<20],*p1=buf,*p2=buf;
6. inline int getc(){
7. return p1==p2&&(p2=(p1=buf)+fread_unlocked(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++;
8. }
9. inline int_fast64_t read(){
10. int_fast64_t a=0;
11. register char c='0';
12. while(c>='0'&&c<='9'){
13. a=(a<<3)+(a<<1)+c-'0';
14. c=getc();
15. }
16. return a;
17. }
18. inline void write(int_fast64_t d){
19. if(d==0){
20. putchar_unlocked(48);
21. return;
22. }
23. int_fast32_t len=0;
24. char n[20];
25. while(d>0){
26. n[len]=d%10+48;
27. len++;
28. d/=10;
29. }
30. for(int i=len-1;i>=0;i--) putchar_unlocked(n[i]);
31. }
32. int main(){
33. int_fast64_t a;
34. while(a=read()){
35. if(a!=1)write(a*a>>2);
36. if(a&1){putchar_unlocked('2'),putchar_unlocked('5'),putchar_unlocked('\n');}
37. else {putchar_unlocked('0'),putchar_unlocked('0'),putchar_unlocked('\n');}
38. }
39. }

補充一個簡單的寫法：__int128
__int128可以存下((2^31)^2)*25
但是它很慢，優化過後才勉強AC

time:1.8s
memory used:1.1MB
code:

1. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
2. #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
3. #pragma comment(linker, "/stack:200000000")
4. #include<ios>
5. char buf[1<<20],*p1=buf,*p2=buf;
6. inline int getc(){
7. return p1==p2&&(p2=(p1=buf)+fread_unlocked(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++;
8. }
9. inline __uint128_t read(){
10. __uint128_t ret=0;
11. uint_fast8_t ch=getc();
12. while(ch>='0'&&ch<='9')
13. ret=(ret<<1)+(ret<<3)+ch-'0',ch=getc();
14. return ret;
15. }
16. inline void write(__uint128_t x){
17. if(x==0){
18. putchar_unlocked(48);
19. return;
20. }
21. uint_fast32_t stk[30],top=0;
22. uint_fast32_t *ptr;
23. ptr=&stk[0];
24. while(x){*ptr=x%10;x/=10;ptr++;}
25. ptr--;
26. while(ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');ptr--;}
27. }
28. int main(){
29. __uint128_t a;
30. while(a=read()){
31. write(a*a*25);
32. putchar_unlocked('\n');
33. }
34. }

Python:

Python已內建大數,直接運算即可

(1)

time(重測後): 5s

memory used: 30.1MB

code:

import sys


while True:


 line=sys.stdin.readline()


 if not line:


  break


 line=int(line)


 print(line*line*25)

(2)

time(重測後): 4.3s

memory used: 32.3MB

code:

import sys


for a in sys.stdin:


 a=int(a)


 print(a*a*25)

本人的分享到此結束
若有更好的想法或建議,請在留言區留言喔