[問題] 蛙跳法 - 二進制+乘法計算
a進位制，1<a<2^31
假設a = 2^30
模數p = 2^31
現有一數k(k=6)寫成二進制，則k = 0110
則需計算
(0*a^1)*(1*a^2)*(1*a^4)*(0*a^8) % p
但是因為a^b數字非常大，會造成溢位
所以需要先計算a^2 % p、a^4 % p
請問，C裡有讀取一個數為二進制時，第幾個數字是0 或 1的語法嗎?
============== Maple蛙跳法程式 ====================
pfrog:=proc(a,b,p)
local frog,n,i,k;
k>1;
k:=convert(convert(b,binary),string); #將k轉成二進制並存成字串
frog[1]:=a:n:=1: #設定乘數
for i from 2 to length(k) do #遞迴儲存A的高次方項
frog[i]:=irem(frog[i-1]* frog[i-1],p);od;
for i from length(k) to 1 by -1 do #計算A^b mod p值
if StringTools[SubString](k,i..i)="1" then n:=irem(n*frog[i], p);fi;od;
end;
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.137.179
※ 編輯: chrisjon 來自: 123.195.137.179 (09/03 15:44)
→
09/03 16:02, , 1F
09/03 16:02, 1F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
