2022年11月9日水曜日

累乗、階乗、C,Pの計算

2^nの計算

ABC256-A

問題概要

2^nを出力せよ。

解答

n=gets.to_i
puts 2.pow(n).to_i
    

としてもいいし、底が2のときたけ使える方法だが、

n=gets.to_i
puts 1<<n
    

としてもいい。

このときは本番不参加。Cでやったのが以下。

int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 4
int main(void){
    char* s1=(char*)malloc(sizeof(char)*N1);
    fgets(s1,N1,stdin);
    int n=readint(s1);
    int t=1,p=2;
    while(n>0){
        if(n%2)t*=p;
        n>>=1;
        p*=p;
    }
    printf("%d\n",t);
    return 0;
}
int readint(char *s){
    int i=0,ret=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}    

累乗

ABC283-A

問題概要

aのb乗を出力せよ。

解答

a,b=gets.chomp.split(" ").map(&:to_i)
puts a**b
    

上が本番で提出したコード。Cでやったのが以下。

int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N 5
int main(void){
    char* s=(char*)malloc(sizeof(char)*N);
    fgets(s,N,stdin);
    int a=readint(s);
    int i=0;
    while(*(s+i)!=32)i++;
    i++;
    int b=readint(s+i);
    free(s);
    int t=1;
    for(int j=0;j<b;j++){
        t*=a;
    }
    printf("%d\n",t);
    return 0;
}
int readint(char *s){
    int i=0,ret=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
    

累乗を求める部分を関数として独立して使えるよ絵にしたのが以下。

#include<stdio.h>
#include<stdlib.h>
#define N 5
int readint(char *s);
int int_pow(int x,int y);
int main(void){
    char* s=(char*)malloc(sizeof(char)*N);
    fgets(s,N,stdin);
    int a=readint(s);
    int i=0;
    while(*(s+i)!=32)i++;
    i++;
    int b=readint(s+i);
    free(s);
    printf("%d\n",int_pow(a,b));
    return 0;
}
int 
int_pow(int x,int n){
    int ret=1; 
    while(n>0){
        if((n&1)==1)ret*=x;
        x*=x;
        n>>=1;
    }
    return ret;
}
int readint(char *s){
    int i=0,ret=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
    

指数関数の不等式を解く

ABC248-B

問題概要

a*k^n≧bを満たす最小の非負整数nを求めよ。(a,b,kは自然数。k≧2)

解答

a,b,k=gets.chomp.split(" ").to_a.map(&:to_i)
i=0
loop do
    if a>=b
        puts i
        exit
    end
    a*=k
    i+=1
end
    

これが本番で提出したコード。

このようにループを回して不等式を満たす最小の整数iを求めたわけだが、直接、上の不等式を解くという方法もある。それでやってみたのが以下のコードなのだが、一つだけWAになった。(Sample:AC x 3,All:AC x 9 WA x 1)

a,b,k=gets.chomp.split(" ").to_a.map(&:to_i)
puts Math::log((b/a.to_f),k).ceil
    

浮動小数点数の誤差の影響かと思うが、確実な理由は分からない。

--------------------

(追記)StackOverflowで質問したところ、やはり浮動小数の誤差が原因だった。


n!を求める

ABC273-A

問題概要

f(0)=1, f(k)=k*f(k-1)である。(k>0) nが与えられたとき、f(n)を求めよ。ただし、n≦10

再帰関数を使ってn!を求める問題である。

解答

    def f(n)
    if n==1 || n==0
        ret=1
    else
        ret=n*f(n-1)
    end
    return ret
end
n=gets.to_i
puts f(n)
    

上は、本番で提出したコード

問題文でもnが10以下という限定が付いているが、この方法でn!を求めると、すぐにnが巨大な数になってしまう。

実用的には、あらかじめn!を小さい順に計算してpushした配列を作っておいて、それを参照するのがよいか。

こんな感じで。

$fac=[]
$fac[0]=1
(1..100).each do |i|
    $fac[i]=$fac[i-1]*i
end
n=gets.to_i
puts $fac[n]
    

Cでやったのが以下。

int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N 4
int main(void){
    char* s=(char*)malloc(sizeof(char)*N);
    fgets(s,N,stdin);
    int n=readint(s);
    free(s);
    int t=1;
    for(int j=1;j<=n;j++){
        t*=j;
    }
    printf("%d\n",t);
    return 0;
}
int readint(char *s){
    int i=0,ret=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
    

パスカルの三角形を描く

ABC254-B

問題概要

次の定義を使ってパスカルの三角形を描け。

  1. j=0またはj=iのとき、a[i,j]=1
  2. 上記以外の時、a[i,j]=a[i-1,j]+a[i-1]

n=gets.to_i
a=[]
n.times do |i|
    a.push(Array.new(i+1,1))
    if i!=0
        (i+1).times do |j|
            if j!=0 && j!=i
                a[i][j]=a[i-1][j-1]+a[i-1][j]
            end
        end
    end
        puts a[i].join(" ")
end
    

問題文の指示通りに実装すればよい。

それ自体としては面白みのない問題だが、これを使ってCの計算をすることができる。

C[n,r]を、C[n,r]=n!/r!・(n-r)!という定義に従って計算しようとすると、途中で出てくる数が大きくなりすぎてしまう難点があるのだが、上のやり方でパスカルの三角形を作れば、a[i-1][j]がそのままC[i,r]になる。

それを使ってCの計算をやってみた。

    
n=100
$a=[]
n.times do |i|
    $a.push(Array.new(i+1,1))
    if i!=0
        (i+1).times do |j|
            if j!=0 && j!=i
                $a[i][j]=$a[i-1][j-1]+$a[i-1][j]
            end
        end
    end
end
def C(n,r)
    if r>n/2
        r=n-r
    end
    $a[n][r]
end
11.times do |i|
    puts "C[10][#{i}]=#{C(10,i)}"
end
    

実行結果は、

C[10][0]=1
C[10][1]=10
C[10][2]=45
C[10][3]=120
C[10][4]=210
C[10][5]=252
C[10][6]=210
C[10][7]=120
C[10][8]=45
C[10][9]=10
C[10][10]=1

Cで書いた、元の問題の解答が以下。

int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 4
int main(void){
    char* s1=(char*)malloc(sizeof(char)*N1);
    if(s1==NULL){
        printf("memory allocation to s1 failed\n");
        exit(1);
    }
    fgets(s1,N1,stdin);
    int n=readint(s1);
    free(s1);
    int sz=n*(n+1)/2;
    int* p=(int*)malloc(sizeof(int)*sz);
    *p=1;
    *(p+1)=1;
    *(p+2)=1;
    int start=3;
    for(int i=2;i<n;i++){
        *(p+start)=1;
        *(p+start+i)=1;
        for(int j=1;j<i;j++){
            *(p+start+j)=*(p+start-i+j-1)+*(p+start-i+j);
//            printf("%d+%d=%d\n",*(p+start-i+j-1),*(p+start-i+j),*(p+start+j));
        }
        start+=(i+1);
    }
    start=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<i+1;j++){
            printf("%d",*(p+start+j));
            if(j==i){
                printf("\n");
            }else{
                printf("%c",32);
            }
        }
        start+=(i+1);
    }
    return 0;
}
int readint(char *s){
    int i=0,ret=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
    

上に手を加えてnCrを求めるものを書いたのが以下。

int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N 30
int main(void){
    int* p=(int*)malloc(sizeof(int)*N*(N+1)/2);
    *p=1;
    *(p+1)=1;
    *(p+2)=1;
    int start=3;
    for(int i=2;i<N;i++){
        *(p+start)=1;
        *(p+start+i)=1;
        for(int j=1;j<i;j++){
            *(p+start+j)=*(p+start-i+j-1)+*(p+start-i+j);
        }
        start+=(i+1);
    }
    for(int i=1;i<N;i++){
        int s=i*(i+1)/2;
        for(int j=0;j<i+1;j++){
            printf("C[%d,%d]=%d\n",i,j,*(p+s+j));
        }
    }
    return 0;
}
int readint(char *s){
    int i=0,ret=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
    

ABC303-B

問題概要

要素数nの整数列がm個与えられる。その中に、一度も隣接していない数字の組はいくつあるか

解答

以下のコードは、一部RE、一部WAになった。

def C(n,r)
    if r==0 || r==n
        return 1
    elsif r==1 || r==n-1
        return n
    else
        return C(n-1,r)+C(n-1,r-1)
    end
end
require 'set'
n,m=gets.chomp.split(" ").map(&:to_i)
a=[]
m.times do |i|
    a[i]=gets.chomp.split(" ").map(&:to_i)
end
b=Array.new(n){Array.new(n,false)}
m.times do |i|
    (n-1).times do |j|
        b[a[i][j]-1][a[i][j+1]-1]=true
        b[a[i][j+1]-1][a[i][j]-1]=true
    end
end
s=Set.new
m.times do |i|
    n.times do |j|
        if b[i][j]==true
            if j<i
                s.add([j,i])
            else
                s.add([i,j])
            end
        end
    end
end
puts C(n,2)-s.size
    

隣接している組の数を数え(たつもりだった)、それを、n人から2人を選ぶ場合の数C[n,2]から引いている。

後から見直してみると上のコードは隣接しているかの判定とは全然関係の無いことをやっているので、やり直したのが以下、これでACになった。

def C(n,r)
    if n<=0 || r<0 || n<r
        puts "wrong argument"
    elsif r==0 || r==n
        return 1
    elsif r==1 || r==n-1
        return n
    else
        return C(n-1,r)+C(n-1,r-1)
    end
end
require 'set'
n,m=gets.chomp.split(" ").map(&:to_i)
ar=[]
m.times do |i|
    ar[i]=gets.chomp.split(" ").map(&:to_i)
end
s=Set.new
m.times do |i|
    (1...n).each do |j|
        a=ar[i][j-1]
        b=ar[i][j]
        if a>b
            a,b=b,a
        end
        s.add([a,b])
    end
end
puts C(n,2)-s.size
=begin
puts C(n,2)
s.each do |st|
    print "(#{st[0]},#{st[1]}), "
end
=end
    

Cでやったのが以下。

int Combi(int n,int r);
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 7
#define N 143
#define N2 5051
int main(void){
    int n,m;
    int i=0;
    char *s=(char*)malloc(sizeof(char)*N1);
    if (s==NULL){
        printf("memory allocation to s failed.\n");
        exit(1);
    }
    fgets(s,N1,stdin);
    n=readint(s);
    while(*(s+i)!=32)i++;
    i++;
    m=readint(s+i);
//    printf("%d %d\n",n,m);
    free(s);
    int* a=(int*)malloc(sizeof(int)*n*m);
    if (a==NULL){
        printf("memory allocation to a failed.\n");
        exit(1);
    }
    for(int j=0;j<m;j++){
        char *s2=(char*)malloc(sizeof(char)*N);
        fgets(s2,N,stdin);
        int l=0,k=0;
        while(k<n){
            int temp=readint(s2+l);
            *(a+j*n+k)=temp; k++;
            while(*(s2+l)>=48 && *(s2+l)<=57)l++;
            l++;
        }
    }
    /*
    for(int j=0;j<m;j++){
        for(int k=0;k<n;k++){
            printf("%d ",*(a+j*n+k));
        }
        printf("\n");
    }
    for(int j=0;j<=10;j++){
        printf("Combi(%d,%d)=%d\n",10,j,Combi(10,j));
    }
    */
    int cnt=0;
    int *b=(int*)malloc(sizeof(int)*N2);
    if (b==NULL){
        printf("memory allocation to b failed.\n");
        exit(1);
    }
    for(int j=0;j<N;j++){
        *(b+j)=0;
    }
    for(int j=0;j<m;j++){
        for(int k=1;k<n;k++){
            int t1=*(a+j*n+k-1);
            int t2=*(a+j*n+k);
            if(t1>t2){
                int temp=t1;
                t1=t2;
                t2=temp;
            }
            int t3=t1*100+t2;
//            printf("(%d, %d)\n",t1,t2);
            *(b+t3)=1;
        }
    }
    for(int j=0;j<N2;j++){
        if(*(b+j)==1)cnt++;
    }
//    printf("Combi(%d,%d)=%d\n",n,2,Combi(n,2));
//    printf("cnt=%d\n",cnt);
    printf("%d\n",Combi(n,2)-cnt);
    return 0;
}
int readint(char *s){
    int i=0,ret=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
int Combi(int n,int r){
    if (n<=0 || r<0 || n<r){
        printf("Wrong argument.\n");
        exit(1);
    }
    if (r==0 || r==n)return 1;
    else if (r==1 || r==n-1)return n;
    else return Combi(n-1,r)+Combi(n-1,r-1);
}
    

基本的にはrubyでやったときと同じやり方で、C(n,2)から隣接している組の数を引いているのだが、問題は、Cでセットを実装する力はまだないということである。しかし、問題においてはnが50とかなり小さいので、隣接する二つの数を、小さい方を上2桁、大きい方を下2桁とする4桁の整数と一対一対応させることができ、二つの数の組を一つの整数に置き換えて著すことができる。そうやって隣接する組の数を数えた。


累乗計算

ABC320-A

問題概要

A^B + B^A を計算せよ。

解答

a,b=gets.chomp.split(" ").map(&:to_i)
puts a**b + b**a
    

Cでやったのが以下。

#include<stdio.h>
#include<stdlib.h>
#define N 5
int readint(char *s);
int int_pow(int x,int y);
int main(void){
    char* s=(char*)malloc(sizeof(char)*N);
    if(s==NULL){
        printf("memory allocation to s failed\n");
        exit(1);
    }
    fgets(s,N,stdin);
    int a=readint(s);
    int i=0;
    while(*(s+i)!=32)i++;
    i++;
    int b=readint(s+i);
    free(s);
    printf("%d\n",int_pow(a,b)+int_pow(b,a));
    return 0;
}
int 
int_pow(int x,int n){
    int ret=1; 
    while(n>0){
        if((n&1)==1)ret*=x;
        x*=x;
        n>>=1;
    }
    return ret;
}
int readint(char *s){
    int i=0,ret=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
    

ABC324-B

問題概要

与えられた整数nが、n=2^x * 3^y と表せるか。

解答

問題は上記のように表現されているが、x,yを具体的に求める必要はなく、要は2と3以外の素因数を持たなければよい。つまり、2と3で割れるだけ割った後、1になっていればよい。

n=gets.to_i
while n%2==0
    n/=2
end
while n%3==0
    n/=3
end
if n==1
    puts "Yes"
else
    puts "No"
end
    

Cでやったのが以下。

#include
#include
#define N 21
long long readll(char *s);
int main(void){
    char* s=(char*)malloc(sizeof(char)*N);
    if(s==NULL){
        printf("memory allocation to s failed\n");
        exit(1);
    }
    fgets(s,N,stdin);
    long long a=readll(s);
    free(s);
    while(a%2==0){
        a=a>>1;
    }
    while(a%3==0){
        a/=3;
    }
    if(a==1){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return 0;
}
long long readll(char *s){
    long long ret=0;
    int i=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
    

ABC327-B

問題概要

与えられた数bが、整数aにより、b=a^a と表せるか。

解答

まずは初めに書いたコード。TLEになった。

b=gets.to_i
if b==1
    puts 1
    exit
else
    (2..(Math::sqrt(b).to_i)).each do |a|
        if a**a==b
            puts a
            exit
        end
    end
end
puts -1
    

まあこれはTLEになるのも当然。B問題だから計算量のことは意識せずに書いたのだが、bは最大で10^18なので、その2乗根まで1つずつ試すと10^9回である。もっとも、この問題の場合、bが4でなければaはbの3乗根以下、27でもなければ4乗根以下なので、その辺までaの上限を下げてしまえば、簡単に回避できそうだ。

そうしてもよかったのだが、上のコードを書きながら、別のやり方もあるなと考えていたので、そちらで書いたのが以下。

    class Pair
    attr_accessor :a, :b
    def initialize(h, t)
        @a, @b = h, t
    end
end
b=gets.to_i
list=[]
a=1
loop do
    t=a**a
    if t&gt;1e18
        break
    else
        list.push(Pair.new(a,t))
        a+=1
    end
end
list.each do |ls|
    if ls.b==b
    puts ls.a
    exit
    end
end
puts -1
    

bは制約により1以上10^18以下だが、何しろbはaの二乗なのでaが大きくなるとすぐにこの上限に達する。なにしろ、a=10ですでにb=10^10なのだ。だから、aを1からはじめて1ずつインクリメントしながらa^aのリストを作っていって、それが10^18を超えたら停止し、リストの中にbが含まれているか調べればよい。出来たリストの中身を確認したところ、aは最大で15だった。


Cでやって、まず書いたのが以下のコード。これはREになった。

typedef struct {
    long long n;
    long long n2;
} table;
long long readll(char *s);
long long ll_pow(long long x, long long n);
#include<stdio.h>
#include<stdlib.h>
#define N1 21
#define N2 16
int main(void){
    char* s1=(char*)malloc(sizeof(char)*N1);
    if(s1==NULL){
        printf("memory allocation to s1 failed\n");
        exit(1);
    }
    fgets(s1,N1,stdin);
    long long  b=readll(s1);
    free(s1);
    table* tb=(table*)malloc(sizeof(table)*N2);
    if(tb==NULL){
        printf("memory allocation to tb failed\n");
        exit(1);
    }
    for(int j=0;j<N2;j++){
        (tb+j)->n=0;
        (tb+j)->n2=0;
    }
    long long t1=1;
    long long t2=1;
    int i=0;
    while(1){
        t2=ll_pow(t1,t1);
        if (t2==0)break; 
        (tb+i)->n=t1;
        (tb+i)->n2=t2;
        t1+=1; i+=1;
    }
/*    for(int i=0;i<N2;i++){
        printf("%d :(%lld, %lld)\n",i+1,(tb+i)->n,(tb+i)->n2);
    }
*/
    int found=0;
    for(int j=0;j<N2;j++){
        if (b==(tb+j)->n2){
            found=1;
            break;
        }
    }
    free(tb);
    if(found==1){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return 0;
}
long long readll(char *s){
    long long ret=0;
    int i=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
long long ll_pow(long long x, long long n){
    long long ret=1; 
    while(n>0){
        if(ret>1e18 || x>1e18){
            return 0;
        }
        if((n&1)==1)ret*=x;
        x*=x;
        n>>=1;
    }
    return ret;
}
    

先にrubyでやったときは、型の最大値を超えてしまうことを心配する必要はなかったが、Cではlong long型の最大値である2^64を超えないようにする必要がある。

もっともこれは、先にrubyでやったときにaが15を超えるとa^aが10^18を超えることを確認しているので、15^15のところまででやめるようにすれば解決可能ではある。しかし、先に型の制約がない言語で一回試しているという前提がない条件で、Cでのコードの中だけで、「long long型の最大値を超えないようにしつつ、bが10^18である場合まですべて漏れなく試す。」という処理を書きたかった。

もちろん、先にrubyで試していなくでも、log10(15^15)=15*log10(15)=15*(log10(3)+1og10(5))=15*(log10(3)+1og10(10/2))=15*(log10(3)+1-1og10(2))=15*(0.4771+1-0.3010)≓17.7, log10(16^16)=log10(2^64)=64*log10(2)=64*0.3010≓19.2となって、15と16の間が境界であることは手計算で確認できる。10^10は明らかに10^18より小さく、20*20=2^20*10^20は明らかに10^18より大きいから、その中間あたりから試していけば、15と16の間が境界というのもすぐわかりはする。ただ、こういう人間による手計算の前処理を使うのもちょっと邪道な気がする。それに、log10(15)やlog10(16)は上のように高校生のころから記憶している数値を使ってすぐに計算できるが、これがlog10(17)やlog10(13)も調べなければならないとなると常用対数表が必要になるし、そういったコードの外の処理を伴わずに、全てをコードの中だけで判定したかったのである。aの上限N2を20としたのは、上述のように20^20が10^18より大きいことは対数計算をするまでもなく明白なので、これぐらいは人間の判断を介在させてもいいだろうと妥協した。

そこで、計算途中で本問のbの制約上の最大値である10^18を超えたら止める処理を累乗を計算する関数であるll_powの中に入れておいたが、なにしろ10^18は2^64にかなり近い数なので(上述のように、log10(2^64)≓19.2)、結局long long型の最大値を超えてしまうのではないかという不安は感じていたが、昨日は頭が疲れていたこともあり、これで提出してしまって、REになったのである。

それで、Stack StackOverflowで質問してしまって終わりにしたのだが、actorbugさんから回答を頂いたところ、やはり計算途中で桁あふれを起こしてしまい、それが原因のようだ。

a=16のとき、ll_pow関数内でi回ループを回した後のxの変化を見てみると

i n x
0 16 16
1 8  16*16=2^8
2 4  (2^8)*(2^8)=2^16
3 2  (2^16)*(2^16)=2^32
4 1  (2^32)*(2^32)=2^64  
    
となり、最後にret=1*2^64=2^64となるが、ここで4回目のループ終了時のxとretに10^18を超える値を代入してしまっている。そして、こうなることは上のコード内のll_pow関数内の処理では止められない。(こんなことは質問する前に自分で気付くべきだった。)

それで、今度はretかxが10^9を超えた時点で止めるようにコードを修正してみたのだが、そうするとnが14と15のときも0を返してまう。

こちらもll_pow関数内でi回ループを回した後のxとretの変化を見てみると、まずa=14のとき、

i   n   x ret
0   14  14  1
1   7   14^2   1
2   1   14^8    14^4   
となって、log10(14^8)=8*log10(14)=8*(log10(2)+log10(7))=8*(0.3010+0.8451)=8*1.1461≓9.2となってxが10^9を超え、ここで終わってしまう。

まずa=15のとき、

i   n   x ret
0   15  15  1
1   7   15^2   15
2   3   15^4    15^2   
3   1   15^8    15^4   
となって、log10(15^8)=8*log10(15)=8*(log10(3)+log10(5))=8*(0.4771+0.6990)=8*1.1761≓9.4となってxが10^9を超え、ここで終わる。

この二つの数の場合には、xが10^10以下まで許容するようにすればうまくいくのだが、そのように人間がいちいちあらかじめ計算して調整することが、果たしてプログラミングのやり方として好ましいものかどうか。

それで、結局、ll_pow関数の中の上限チェックの部分は削除し、aを15まで試して止めることにした。これでACになった。それが以下。なお、先のコードは解答の形式も違っていたので、そこも修正してある。

typedef struct {
    long long n;
    long long n2;
} table;
long long readll(char *s);
long long ll_pow(long long x, long long n);
#include<stdio.h>
#include<stdlib.h>
#define N1 21
#define N2 15
int main(void){
    char* s1=(char*)malloc(sizeof(char)*N1);
    if(s1==NULL){
        printf("memory allocation to s1 failed\n");
        exit(1);
    }
    fgets(s1,N1,stdin);
    long long  b=readll(s1);
    free(s1);
    table* tb=(table*)malloc(sizeof(table)*N2);
    if(tb==NULL){
        printf("memory allocation to tb failed\n");
        exit(1);
    }
    for(int j=0;j<N2;j++){
        (tb+j)->n=0;
        (tb+j)->n2=0;
    }
    long long t1=1;
    long long t2=1;
    int i=0;
    for(int j=0;j<N2;j++){
        t2=ll_pow(t1,t1);
        (tb+j)->n=t1;
        (tb+j)->n2=t2;
        t1+=1;
    }
/*    for(int i=0;i<N2;i++){
        printf("%d :(%lld, %lld)\n",i+1,(tb+i)->n,(tb+i)->n2);
    }
*/
    int found=-1;
    for(int j=0;j<N2;j++){
        if (b==(tb+j)->n2){
            found=(tb+j)->n;
            break;
        }
    }
    free(tb);
    printf("%d\n",found);
    return 0;
}
long long readll(char *s){
    long long ret=0;
    int i=0;
    while(*(s+i)>=48 && *(s+i)<=57){
        ret*=10;
        ret+=*(s+i)-48;
        i+=1;
    }
    return ret;
}
long long ll_pow(long long x, long long n){
    long long ret=1; 
    while(n>0){
        if((n&1)==1)ret*=x;
        x*=x;
        n>>=1;
    }
    return ret;
}
    

0 件のコメント:

コメントを投稿