POJ 2109 Power of Cryptography【高精度+二分 Or double水过~~】

时间:2021-03-11 10:07:09

题目链接:

http://poj.org/problem?id=2109

参考:

http://blog.csdn.net/code_pang/article/details/8263971

题意:

给定n,p,求k使得kn=p(1≤n≤200, 1≤p<10101, 1≤k≤109)

分析:

高精度+二分~~

k的位数为p的位数除以n的向上取整,这样知道k的位数便可以在范围内二分了~注意这里的答案是向下取整~~

代码:

#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
const int maxn = 205;
char p[maxn];
class BigNum
{
private:
int a[500];
int len;
public:
BigNum(){
len = 1;
memset(a, 0 ,sizeof(a));
}
BigNum(const int);
BigNum(const char*);
BigNum(const BigNum &);
BigNum &operator = (const BigNum &); BigNum operator +(const BigNum &)const ;
BigNum operator*(const BigNum &)const ;
BigNum operator^(const int &)const ;
bool operator >(const int &)const;
bool operator >(const BigNum &T)const; void print();
};
BigNum::BigNum(const int b)
{
int c, d = b;
len = 0;
while(d > MAXN){
c = d % (MAXN + 1);
d = d / (MAXN + 1);
a[len++] = c;
}
a[len++] = d;
}
BigNum::BigNum(const char*s)
{
int t, k, index;
memset(a,0,sizeof(a));
int l = strlen(s);
len = l / DLEN;
if(l % DLEN)
len++;
index=0;
for(int i = l - 1; i >= 0; i -= DLEN){
t = 0;
k = i - DLEN + 1;
if(k<0) k=0;
for(int j = k; j <= i; j++)
t = t * 10 + s[j] - '0';
a[index++] = t;
}
}
BigNum::BigNum(const BigNum & T) : len(T.len)
{
memset(a, 0, sizeof(a));
for(int i = 0 ; i < len ; i++)
a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n)
{
len = n.len;
memset(a, 0, sizeof(a));
for(int i = 0 ; i < len ; i++)
a[i] = n.a[i];
return *this;
}
BigNum BigNum::operator+(const BigNum & T) const
{
BigNum t(*this);
int big; //位数
big = T.len > len ? T.len : len;
for(int i = 0; i < big; i++){
t.a[i] +=T.a[i];
if(t.a[i] > MAXN){
t.a[i + 1]++;
t.a[i] -=MAXN+1;
}
}
if(t.a[big] != 0) t.len = big + 1;
else t.len = big;
return t;
}
BigNum BigNum::operator*(const BigNum & T) const
{
BigNum ret;
int up;
int temp,temp1;
int i, j;
for(i = 0 ; i < len ; i++){
up = 0;
for(j = 0 ; j < T.len ; j++){
temp = a[i] * T.a[j] + ret.a[i + j] + up;
if(temp > MAXN){
temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
up = temp / (MAXN + 1);
ret.a[i + j] = temp1;
}
else{
up = 0;
ret.a[i + j] = temp;
}
}
if(up != 0)
ret.a[i + j] = up;
}
ret.len = i + j;
while(ret.a[ret.len - 1] == 0 && ret.len > 1)
ret.len--;
return ret;
}
BigNum BigNum::operator^(const int & n) const
{
BigNum t,ret(1);
if(n < 0) exit(-1);
if(n == 0) return 1;
if(n == 1) return *this;
int m = n;
int i;
while(m > 1){
t = *this;
for(i = 1; i<<1<=m; i <<= 1)
t = t * t;
m -= i;
ret = ret * t;
if(m == 1) ret=ret*(*this);
}
return ret;
}
bool BigNum::operator>(const BigNum & T) const
{
int ln;
if(len > T.len)
return true;
else if(len == T.len){
ln = len - 1;
while(a[ln] == T.a[ln] && ln >= 0)
ln--;
if(ln >= 0 && a[ln] > T.a[ln])
return true;
else
return false;
}
else
return false;
}
bool BigNum::operator >(const int & t) const
{
BigNum b(t);
return *this>b;
}
void BigNum::print()
{
printf("%d",a[len-1]);
for(int i = len - 2 ; i >= 0 ; i--) printf("%04d",a[i]);
printf("\n");
}
int main(void)
{
int n, len, MIN, MAX, MID;
while(~scanf("%d%s", &n, &p)){
len = (int)ceil((double)strlen(p) / n);
MIN = 1, MAX = 9;
for(int i = 0; i < len - 1; i++){
MAX *= 10;
MAX += 9;
MIN *= 10;
}
while(MIN < MAX){//[]
MID = (MIN + MAX) / 2;
if(BigNum(p) > (BigNum(MID) ^ n)) MIN = MID +1;
else if((BigNum(MID) ^ n) > BigNum(p)) MAX = MID - 1;
else break;
}
if(MAX == MIN) MID = MIN;
if((BigNum(MID) ^ n) > BigNum(p)) MID--;
printf("%d\n",MID);
}
return 0;
}

代码:

double类型能表示10−307到10308, 足够这个题用。

而double超过16位后面都变成0,这样正好满足向下取整。

12337=4332529576639313702577

12347=4357186184021382204544

12357=4381962969567270546875

值不同的地方(从高到低第三位)没有超过double的精度,所以不会导致错误答案~

#include<iostream>
#include<cmath>
using namespace std;
int main (void)
{
double n, m;
while(cin>>n>>m){
cout<<pow(m, 1/n)<<endl;
}
return 0;
} //或者 #include<iostream>
#include<cmath>
using namespace std;
int main (void)
{
double n, p;
while(cin>>n>>p){
cout<< exp(log(p)/n) <<endl;
}
return 0;
}
//pow明显更快,只是想说明有时候取对数也是个不错的方法~

POJ 2109 Power of Cryptography【高精度+二分 Or double水过~~】的更多相关文章

  1. POJ - 2109 Power of Cryptography&lpar;高精度log&plus;二分&rpar;

    Current work in cryptography involves (among other things) large prime numbers and computing powers ...

  2. POJ 2109 Power of Cryptography 大数&comma;二分&comma;泰勒定理 难度&colon;2

    import java.math.BigInteger; import java.util.Scanner; public class Main { static BigInteger p,l,r,d ...

  3. 贪心 POJ 2109 Power of Cryptography

    题目地址:http://poj.org/problem?id=2109 /* 题意:k ^ n = p,求k 1. double + pow:因为double装得下p,k = pow (p, 1 / ...

  4. POJ 2109 -- Power of Cryptography

    Power of Cryptography Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 26622   Accepted: ...

  5. POJ 2109 Power of Cryptography 数学题 double和float精度和范围

    Power of Cryptography Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 21354 Accepted: 107 ...

  6. poj 2109 Power of Cryptography

    点击打开链接 Power of Cryptography Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 16388   Ac ...

  7. poj 2109 Power of Cryptography &lpar;double 精度&rpar;

    题目:http://poj.org/problem?id=2109 题意:求一个整数k,使得k满足kn=p. 思路:exp()用来计算以e为底的x次方值,即ex值,然后将结果返回.log是自然对数,就 ...

  8. Poj 2109 &sol; OpenJudge 2109 Power of Cryptography

    1.Link: http://poj.org/problem?id=2109 http://bailian.openjudge.cn/practice/2109/ 2.Content: Power o ...

  9. POJ 2109 :Power of Cryptography

    Power of Cryptography Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 18258   Accepted: ...

随机推荐

  1. &lbrack;DataTable&rsqb;控件排序事件中用DataView及DataTable排序

    控件排序事件中用DataView及DataTable排序 文章分类:.net编程 在做ASP.NET页面开发时,经常要用到dataset(或者DataTable),绑定到DataGrid或GridVi ...

  2. 判断浏览器是否支持某个css属性

    方法:直接判断浏览器是否支持某个CSS属性才是王道,document.documentElement.style 如:判断是否支持 transform if( 'MozTransform' in do ...

  3. C&plus;&plus;STL之String

    本文直接转载,非原创!仅记录供自己学习之用. 出处:http://blog.csdn.net/y990041769/article/details/8763366 在学习c++STL中的string, ...

  4. Java 第五周总结

    1. 本周学习总结 2. 书面作业 1.代码阅读:Child压缩包内源代码 1.1 com.parent包中Child.java文件能否编译通过?哪句会出现错误?试改正该错误.并分析输出结果. 不能. ...

  5. 微信昵称有特殊符号怎么保存到mysql库里?

    微信昵称有特殊符号怎么保存到mysql库里? mysql库怎么保存emoji表情? 这里提供 1 种稳妥有效的方法: // 入库之前,使用 Base64 编码 String nickname = re ...

  6. CentOS 7 MySQL HA之DRBD

    一.DRBD简介 DRBD的全称为:Distributed ReplicatedBlock Device(DRBD)分布式块设备复制,DRBD是由内核模块和相关脚本而构成,用以构建高可用性的集群.其实 ...

  7. ES6 新增数据类型检测 Set Map Proxy

    检测代码方法 function isNative(api){ return /native code/.test(api.toString())&&typeof api !== 'un ...

  8. MySQL常用shell语句

    1.连接数据库 格式:mysql -h ip -P port -u user -p 2.修改某一列的值 格式:update tablename set column1 = 'xxx', column2 ...

  9. 详解UML图之类图 (转)

    原址: https://www.jianshu.com/p/4cd95d4ddb59 2.  怎么画类图?用什么工具? 使用工具:Visio或者processon在线作图 在类图中一共包含了以下几种模 ...

  10. 疯狂java学习笔记

    面向对象: 从现实世界中客观存在的事物(对象)出发构造软件系统,并在软件系统构造中运用人类的自然思维方式,强调直接以现实世界中的事物为中心来思考,认识问题,并根据这些事务的本质特点,将他们抽象为系统中 ...