|
今天在刷洛谷的时候，正巧发现在普及题库中的p1045非常的有意思，可以从某种意义上相似于大数相加，但经过仔细思考便发现并不是这样简单的情况，这个题目要求的如果考虑的太少的话会导致循环中的次数太多，从而不可以很好的解决，只能花费大量的时间和空间进行一步一步的运算，大概估计便可以得到这个一定会导致结果的失败，那么不如利用其他方法
快速幂的运算是在这种情况下比较好的一种情况。
正如大家所知道的，在a进行自我的平方运算的时候，自乘的结果可以在自乘n次的情况下得到a的二的n次方，同时也有a的x次方和a的y次方进行运算，可以得到a的x+y次方。
那么就有个例子，假如是a的12次方，设b=12,那么便可以得到12的十进制转化二进制可以得到二进制的1100。那么从左到右便可以认为是a的十二次方等同于a的八次方加上a的四次方，
那么便可以得到准备答案。
在这个过程当中，我们要做到在计算的时候实现次数的减少
在网上存在一个简单的计算
while(b > 0)
{
if(b & 1)
ans *= base;
/*关于 b & 1：
“&”美名曰“按位与”。
x & y 是二进制 x 和 y 的每一位分别进行“与运算”的结果。
与运算，即两者都为 1 时才会返回 1，否则返回 0。
那么 b & 1
二进制
b = 1011
1 = 0001
b&1 = 0001
因为 1（二进制）的前面几位全部都是 0，
所以只有 b 二进制最后一位是 1 时，b & 1 才会返回 1。
挺巧妙的，并且很快。)*/
base *= base;
b >>= 1;
}
我写的相比这个会更麻烦一些，?
#include<iostream>//求a的b次方
using namespace std;
void dectobin(int b)
{
int sum = 0;
int y, x = 1; // y表示余数，x为叠加的系数
while (b != 0)
{
y = b % 2;
sum += x * y;
x *= 10;
b /= 2;
}
b=sum;
}
int main(){
int a,b;
double n=1;
cin>>a>>b;
dectobin(b);
while(b>0){
if(b&1){
n *=a;
}
a *=a;
b>>=1;
}
return n;
}
?但相同的可以解决这个问题，只不过需要稍微对这个代码进行修饰
便可以得到这样的结果
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
ll b,p,k,ans;
cin>>b>>p>>k;
ans=1;
cout<<b<<"^"<<p<<" mod "<<k<<"=";
while(p > 0){
if(p & 1)//b的二进制末尾为1，即奇数
ans = ans * b % k;
b = b * b % k;
p >>= 1;//将b的二进制向右移1位数
}
cout<<ans%k;
return 0;
}
可以说是很简单的解决方法，那么再利用这个先通过p1226
然后可以利用这个代码解决p1045的问题，?观察题目他给的数据十分简单，只有简单的几个要求
文件中只包含一个整数PP（1000<P<31000001000<P<3100000）
输出格式
第一行：十进制高精度数2^{P}-12P?1的位数。
第2-11行：十进制高精度数2^{P}-12P?1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）
不必验证2^{P}-12P?1与PP是否为素数。
?
这个题说的是麦森书但在输出格式上并没有何其有太大的关系感觉。我在这里可以用更简单的方法对这个进行更改。
在第一个要求输出的在题解中有一个大神给出了很简洁的解决方法
s=n*log10(2)+1;用函数算位数
cout<<s<<endl;
这种行为感觉真的是大神。。。
那么接下来便是对于第二问的解决
?
while(n>=20){
k=0;
for(i=1;i<=50&&i<=top;i++){//数组的每一个元素里放十位数
a[i]=(a[i])<<20+k;//每次乘上2的20次方：1048576 把longlong剩余9位用到位
k=a[i]/10000000000;a[i]%=10000000000;//进位
if(top<50&&k&&i==top)top++;//加位数 ，前面s算过了 可以省
}
n-=20;//一次算20个
}
while(n){//把20个以下的依次算完
k=0;
for(i=1;i<=50&&i<=top;i++){
a[i]=a[i]<<1+k;
k=a[i]/10000000000;a[i]%=10000000000;//用法同上
if(top<50&&k&&i==top)top++;
}
n--;
}
a[1]--;
if(top<50){
i=top+1;//可以用s
while(i<=50){//小于500位，要加前导零
for(j=1;j<=5&&i<=50;i++,j++)cout<<"0000000000";
if(j==6)cout<<endl;
}
i=top;
for(;j<=5&&i>=1;i--,j++){//注意：50位一行！！！j<=5!!!
if(a[i]>=1000000000)cout<<a[i];
else{
s=a[i];
while(s>0){s/=10;o++;}
o=10-o;
while(o>0){o--;cout<<"0";}
cout<<a[i];
}
}
cout<<endl;
while(i>=1){//注意：大于五百位也有可能有前导零
for(j=1;j<=5&&i>=1;i--,j++){//是每一个元素（10位）中的的前导零
if(a[i]>1000000000)cout<<a[i];//判断是否有前导零
else{
s=a[i];
while(s>0){s/=10;o++;}//记录前导零个数
o=10-o;
while(o>0){o--;cout<<"0";}//输出
cout<<a[i];
}
}
cout<<endl;
}
}
else{
s=a[50];
i=50;
while(i>=1){
for(j=1;j<=5&&i>=1;i--,j++){
if(a[i]>1000000000)cout<<a[i];
else{
s=a[i];
while(s>0){s/=10;o++;}// 这一段用法同上
o=10-o;
while(o>0){o--;cout<<"0";}
cout<<a[i];
}
}
cout<<endl;
}
}
return 0;
}
这个是大神的代码，但我现在使用的是快速幂，也可以稍微简单的解决
#include<bits/stdc++.h>
const long long mod=10000000000;
using namespace std;
const int N=1e5+10;
int P, l=1,lb=1;
int a[N]= {},b[N]= {},c[N]={};
int cheng1() {
memset(c,0,sizeof(c));
for (int i = 1; i <= l; ++i) {
for (int j = 1; j <= lb; ++j) {
c[i+j-1] += a[i] * b[j];
c[i+j] += ( c[i+j-1] ) / 10;
c[i+j-1] %= 10;
}
}
int lc = l + lb;
while( c[lc] == 0 ) -- lc;
for(int i = 1;i <= lc; ++i){
a[i] = c[i];
}
return lc;
}
int cheng2() {
memset(c,0,sizeof(c));
for (int i = 1; i <= lb; ++i) {
for (int j = 1; j <= lb; ++j) {
c[i+j-1] += b[i] * b[j];
c[i+j] += ( c[i+j-1] ) / 10;
c[i+j-1] %= 10;
}
}
int lc = lb + lb;
while( c[lc] == 0 ) -- lc;
for(int i = 1;i <= lc; ++i){
b[i] = c[i];
}
return lc;
}
int main() {
memset( a, 0, sizeof(a));
memset( a, 0, sizeof(b));
scanf("%d",&P);
a[1] = 1;
b[1] = 2;
-- a[1];
for (int i = 500; i >= 1; --i) {
printf("%d",a[i]);
if ( ! ( (i-1) % 50 ) ) printf("\n");
}
return 0;
}
?
?
|