当前位置:网站首页>P1045 Mason number (number theory & high precision)

P1045 Mason number (number theory & high precision)

2021-08-10 08:05:04 wx6110fa547fd20

P1045 Mason number ( number theory & Hyperfine )

  Subject portal

The question :2 ^ p-1 And output 500 digit
Ideas :2 ^ p-1 And 2 ^ p The same number of digits ( because 2 ^ p The number of digits is not 0), So will 2 ^ p Convert to 10 ^ n The form can be

 Insert picture description here

AC Code :

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int ans[N],tmp[N],a[N],p;
void muti(int *x,int *y){ // Hyperfine x*y 
	memset(tmp,0,sizeof tmp);
	for(int i=1;i<=500;i++)
		for(int j=1;j<=500;j++)
			tmp[i+j-1]+=x[i]*y[j];
	for(int i=1;i<=500;i++)
	{
		tmp[i+1]+=tmp[i]/10;
		tmp[i]%=10;
	}
	memcpy(ans,tmp,sizeof a);
}
void fun(int *f){ // High precision square  
	memset(tmp,0,sizeof tmp);
	for(int i=1;i<=500;i++)
		for(int j=1;j<=500;j++)
			tmp[i+j-1]+=f[i]*f[j];
	for(int i=1;i<=500;i++)
	{
		tmp[i+1]+=tmp[i]/10;
		tmp[i]%=10;
	}
	memcpy(a,tmp,sizeof a);
}  
void ksm(int *x,int n){ // Fast power  
	while(n){
		if(n&1) muti(ans,x);
		fun(x);
		n>>=1;
	}
}
int main(){
	cin>>p;
	cout<<(int)(log10(2)*p+1)<<endl;// Find digit  
	a[1]=2,ans[1]=1;// initialization  
	ksm(a,p);
	ans[1]-=1;
	for(int i=500;i>=1;i--){
		if(i<500&&i%50==0) printf("\n%d",ans[i]);// Control format  
		else printf("%d",ans[i]);
	}
	return 0;
} 

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810080205610Z.html

随机推荐