|
投稿者：山中和義
投稿日：2013年12月21日(土)10時45分20秒
|
|
|
|
031
両替問題
考察
5p貨までの使用枚数が決まれば、1p貨の使用枚数は自動的に決まるので、
1p貨を何枚使うかは考える必要がない。
したがって、問題を置き換えて、
5p貨までを使用して、0～200￡を支払う場合の数を求めればよい。
（終り）
!!OPTION ARITHMETIC RATIONAL !多桁の整数
LET M=200
LET S=0
FOR C200=0 TO M STEP 200 !0,200,…
LET T200=M-C200 !残りの金額について
FOR C100=0 TO T200 STEP 100
LET T100=T200-C100
FOR C50=0 TO T100 STEP 50
LET T50=T100-C50
FOR C20=0 TO T50 STEP 20
LET T20=T50-C20
FOR C10=0 TO T20 STEP 10
LET T10=T20-C10
FOR C5=0 TO T10 STEP 5
LET T5=T10-C5
LET S=S+INT(T5/2)+1
NEXT C5
NEXT C10
NEXT C20
NEXT C50
NEXT C100
NEXT C200
PRINT S;"通り" !73682通り
END
|
|
|
|
投稿者：山中和義
投稿日：2013年12月21日(土)10時49分26秒
|
|
|
|
> No.3244[元記事へ]
046
Christian Goldbachは、全ての奇合成数は平方数の2倍と素数の和で表せると予想した。
参考サイト http://odz.sakura.ne.jp/projecteuler/
OPTION ARITHMETIC RATIONAL !多桁の整数
FOR N=1 TO 100000 STEP 2
LET K=1
LET T=N-2*K^2
DO WHILE T>1 AND prmdiv(T)<>T
LET K=K+1
LET T=N-2*K^2
LOOP
IF T<0 THEN PRINT N
NEXT N
END
!UBASICの整数論関連より UBASIC.LIB抜粋
EXTERNAL FUNCTION prmdiv(n) !１より大きな最小の約数
OPTION ARITHMETIC RATIONAL !多桁の整数
IF n<>INT(n) THEN !整数以外なら
PRINT "prmdiv関数でパラメータが不適当です。"
STOP
ELSEIF n=0 THEN
LET prmdiv=0
ELSE
LET n=ABS(n) !絶対値をとる
IF MOD(n,2)=0 THEN !２の倍数
LET prmdiv=2
ELSEIF MOD(n,3)=0 THEN !３の倍数
LET prmdiv=3
ELSE
FOR i=5 TO INTSQR(n) STEP 6
IF MOD(n,i)=0 THEN !5,11,17,23,29,…
LET prmdiv=i
EXIT FUNCTION
ELSEIF MOD(n,i+2)=0 THEN !7,13,19,25,31,…
LET prmdiv=i+2
EXIT FUNCTION
END IF !+1,+3,+5は２の倍数（偶数）、+1,+4は３の倍数、+5は５の倍数
NEXT i
LET prmdiv=n !その数自身
END IF
END IF
END FUNCTION
003
素因数分解
OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=13195
LET N=600851475143
DO
LET P=prmdiv(N)
DO WHILE MOD(N,P)=0 !p^k
LET N=N/P
LOOP
LOOP WHILE N>1
PRINT P !6857
END
010
素数の和
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=2
FOR N=3 TO 2000000 STEP 2
IF prmdiv(N)=N THEN LET S=S+N
NEXT N
PRINT S !142913828922
END
|
|
|
|
投稿者：山中和義
投稿日：2013年12月21日(土)11時13分35秒
|
|
|
|
> No.3245[元記事へ]
024
順列
0～9の10個の数字の順列を辞書順に並べ替えたときに、100万個目の文字列は何か。
LET N=10
DIM A(N) !1～10の並び
CALL Num2PermFactorial(1000000-1, A,N)
FOR i=1 TO N !0相対
LET A(i)=A(i)-1
NEXT i
MAT PRINT A;
END
!n!の順列パターン ⇔ 0～(n!-1)の番号
EXTERNAL FUNCTION PermFactorial2Num(A(),N) !順列パターンに番号を付ける ※辞書式順序
FOR j=1 TO N-1 !階乗進数の各桁の値＋１ A[1..N]=(N-1)! … 3! 2! 1! 0!
FOR k=j+1 TO N
IF A(k)>=A(j) THEN LET A(k)=A(k)-1
NEXT k
NEXT j
LET v=0
FOR j=N TO 1 STEP -1 !非負の10進数整数へ
LET v=v*j+A(N-j+1)-1
NEXT j
LET PermFactorial2Num=v
END FUNCTION
EXTERNAL SUB Num2PermFactorial(h, A(),N) !番号から順列パターンを生成する ※辞書式順序
LET v=h !非負の10進数整数を階乗進数へ
FOR j=1 TO N
LET t=INT(v/j)
LET A(N-j+1)=v-t*j +1 !階乗進数の各桁の値＋１ A[1..N]=(N-1)! … 3! 2! 1! 0!
LET v=t
NEXT j
FOR j=N-1 TO 1 STEP -1 !順列パターンへ
FOR k=j+1 TO N
IF A(k)>=A(j) THEN LET A(k)=A(k)+1
NEXT k
NEXT j
END SUB
|
|
|
|
投稿者：山中和義
投稿日：2013年12月22日(日)11時00分8秒
|
|
|
|
> No.3246[元記事へ]
001
1000未満の3か5の倍数になっている数字の合計を求めよ。
!!OPTION ARITHMETIC RATIONAL !多桁の整数
!その１
LET S=0
FOR N=1 TO 1000-1
IF MOD(N,3)=0 OR MOD(N,5)=0 THEN LET S=S+N
NEXT N
PRINT S !233168
!その２
DEF F(N)=N*(N+1)/2
LET N=1000-1
PRINT 3*F(INT(N/3))+5*F(INT(N/5))-15*F(INT(N/15))
END
|
|
|
|
投稿者：山中和義
投稿日：2013年12月22日(日)11時01分34秒
|
|
|
|
> No.3247[元記事へ]
002
偶数のフィボナッチ数
考察
奇数+偶数=奇数 1+2=3
偶数+奇数=奇数 2+3=5
奇数+奇数=偶数 3+5=8
（終り）
!!OPTION ARITHMETIC RATIONAL !多桁の整数
LET F1=1
LET F2=2
LET S=0
DO WHILE F2<4000000
LET S=S+F2
PRINT F2 !debug
LET F4=2*F2+F1 !F3=F2+F1、F4=F3+F2、F5=F4+F3より
LET F5=3*F2+2*F1
LET F1=F4
LET F2=F5
LOOP
PRINT S !4613732
END
|
|
|
|
投稿者：山中和義
投稿日：2013年12月22日(日)11時08分34秒
|
|
|
|
> No.3248[元記事へ]
006
2乗和の差
OPTION ARITHMETIC RATIONAL !多桁の整数
!その１
LET N=100
PRINT (N*(N+1)/2)^2 - N*(N+1)*(2*N+1)/6 !(Σk)^2-Σk^2
!その２
LET N=100
LET S=0 !(1+2+3+ … +100)^2-(1^2+2^2+3^2+ … +100^2)
FOR A=1 TO N-1
FOR B=A+1 TO N
LET S=S+A*B
NEXT B
NEXT A
PRINT 2*S !25164150
END
|
|
|
|
投稿者：山中和義
投稿日：2013年12月23日(月)10時39分43秒
|
|
|
|
> No.3249[元記事へ]
005
1から20までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか。
!!OPTION ARITHMETIC RATIONAL !多桁の整数
DEF LCM(a,b)=a*b/GCD(a,b) !最小公倍数
LET L=1 !最小の数
FOR i=2 TO 20
LET L=LCM(L,i)
NEXT i
PRINT L
PRINT 2^4*3^2*5*7*11*13*17*19 !検算
END
EXTERNAL FUNCTION gcd(a,b) !最大公約数
DO UNTIL b=0
LET t=b
LET b=MOD(a,b)
LET a=t
LOOP
LET gcd=ABS(a)
END FUNCTION
|
|
|
|
投稿者：山中和義
投稿日：2013年12月23日(月)10時41分28秒
|
|
|
|
> No.3250[元記事へ]
015
20×20 のマス目ではいくつのルートがあるか。
!!OPTION ARITHMETIC RATIONAL !多桁の整数
PRINT FACT(20+20)/(FACT(20)*FACT(20))
PRINT COMB(20+20,20)
LET N=20+20
LET R=20
LET C=1
FOR i=1 TO R !nCr=nPr/r!={ n*(n-1)* … *(n-r+1) } / { 1*2* … *r }
LET C=C*(N-i+1)/i
NEXT i
PRINT C
END
|
|
|
|
投稿者：山中和義
投稿日：2013年12月23日(月)10時43分29秒
|
|
|
|
> No.3251[元記事へ]
040
チャンパーノウン定数
考察
1桁の数（1～9）が、9個
2桁の数（10～99）が、90個
3桁数の数（100～999）が、900個
4桁数の数（1000～9999）が、9000個
：
ずつ並んでいく。
（終り）
!!OPTION ARITHMETIC RATIONAL !多桁の整数
PRINT f(1)*f(10)*f(100)*f(1000)*f(10000)*f(100000)*f(1000000)
END
EXTERNAL FUNCTION f(N) !小数点以下第n位にある数字を返す
LET T=N
LET K=1 !該当する数の桁数
DO
LET W=K*9*10^(K-1)
IF T<=W THEN EXIT DO
LET T=T-W
LET K=K+1
LOOP
!!!PRINT K; T !debug
LET Q=CEIL(T/K)
LET A=10^(K-1)+Q-1 !該当する数
LET R=MOD(T,K) !桁位置
IF R=0 THEN LET R=K
LET B=10^(K-R)
LET W=MOD(INT(A/B),10)
!!!PRINT Q;R; A;B ;W !debug
LET f=W
END FUNCTION
|
|
|
|
投稿者：山中和義
投稿日：2013年12月25日(水)13時59分46秒
|
|
|
|
> No.3252[元記事へ]
016
累乗の各桁の和
2^1000の各桁の和を求めよ。
OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=2^1000
!!LET N=2^15
PRINT N !debug
LET S=0
DO WHILE N>0
LET S=S+MOD(N,10)
LET N=INT(N/10)
LOOP
PRINT S !1366
END
020
階乗の数字和
100!の各桁の数字の和を求めよ。
OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=FACT(100)
!!LET N=FACT(10)
PRINT N !debug
LET S=0
DO WHILE N>0
LET S=S+MOD(N,10)
LET N=INT(N/10)
LOOP
PRINT S !648
END
025
1000桁のフィボナッチ数
OPTION ARITHMETIC RATIONAL !多桁の整数
LET F1=1
LET F2=1
LET K=2 !k項
DO WHILE INT(F2/10^(1000-1))=0
LET K=K+1
LET F3=F2+F1
LET F1=F2
LET F2=F3
LOOP
PRINT K !4782
END
十進BASICは、有理数モードで多桁整数が扱えるので上記のように記述すればよい。
多桁整数を実装する場合は次のようにする。
016
LET N=1000 !2^n
DIM A(1000) !10進法k桁の数 a[k]*10^(k-1)+ … +a[2]*10^1+a[1]*10^0、0≦a[j]≦9
MAT A=ZER
LET A(1)=2 !2^1=2とする
FOR i=2 TO N !2^n
CALL MUL(A,2)
NEXT i
LET S=0 !各桁の数字の和
FOR i=1 TO 1000
LET S=S+A(i)
NEXT i
PRINT S
END
EXTERNAL SUB MUL(A(),X) !かけ算 A=A*X
LET CY=0 !かけ算の筆算による
FOR J=1 TO 1000 !j桁目を計算する
LET T=A(J)*X+CY
LET A(J)=MOD(T,10)
LET CY=INT(T/10)
NEXT J
IF CY>0 THEN
PRINT "オーバーフロー"
STOP
END IF
!!!MAT PRINT A; !debug
END SUB
020
LET N=100 !n!
DIM A(1000) !10進法k桁の数 a[k]*10^(k-1)+ … +a[2]*10^1+a[1]*10^0、0≦a[j]≦9
MAT A=ZER
LET A(1)=1 !0!=1!=1とする
FOR X=2 TO N !2*3*4* … *n
CALL MUL(A,X)
NEXT X
LET S=0 !各桁の数字の和
FOR i=1 TO 1000
LET S=S+A(i)
NEXT i
PRINT S
END
025
DIM F1(1000),F2(1000),F3(1000)
MAT F1=ZER
LET F1(1)=1
MAT F2=ZER
LET F2(1)=1
LET K=2 !k項
LET F=F2(1000) !1000桁目の値
DO WHILE F=0
LET K=K+1
SELECT CASE MOD(K,3) !F[n+2]=F[n+1]+F[n]
CASE 0
CALL ADD(F2,F1, F3)
LET F=F3(1000)
CASE 1
CALL ADD(F3,F2, F1)
LET F=F1(1000)
CASE 2
CALL ADD(F1,F3, F2)
LET F=F2(1000)
CASE ELSE
END SELECT
LOOP
PRINT K !4782
END
EXTERNAL SUB ADD(A(),B(), C()) !足し算 C=A+B
LET CY=0
FOR i=1 TO 1000 !i桁目を計算する
LET T=A(i)+B(i)+CY
LET C(i)=MOD(T,10)
LET CY=INT(T/10)
NEXT i
IF CY>0 THEN
PRINT "オーバーフロー"
STOP
END IF
END SUB
|
|
|
|
投稿者：山中和義
投稿日：2013年12月25日(水)19時55分8秒
|
|
|
|
> No.3257[元記事へ]
206
2乗すると「1_2_3_4_5_6_7_8_9_0」の形となるような唯一の正整数を求めよ。
ただし、「_」は1桁の数である。
考察
2乗すると0になるのは、0のみである。
2乗すると9になるのは、3と7のみである。
求める値は、一の位が0で、十の位は3または7である。
よって、2乗すると「1_2_3_4_5_6_7_8_900」の形となる。
これより、「1_2_3_4_5_6_7_8_9」として、
√(10203040506070809)から√(19293949596979899)までの範囲である。
（終り）
OPTION ARITHMETIC RATIONAL !多桁の整数
FOR M=INT(INTSQR(10203040506070809)/10) TO INTSQR(19293949596979899)/10
LET N=M*10+3
LET T=N*N
FOR i=9 TO 1 STEP -1
IF MOD(T,10)<>i THEN EXIT FOR
LET T=INT(T/100)
NEXT i
IF i<1 THEN PRINT N*10
LET N=M*10+7
LET T=N*N
FOR i=9 TO 1 STEP -1
IF MOD(T,10)<>i THEN EXIT FOR
LET T=INT(T/100)
NEXT i
IF i<1 THEN PRINT N*10 !1389019170^2=1929374254627488900
NEXT M
END
|
|
|
|
投稿者：山中和義
投稿日：2013年12月27日(金)09時50分25秒
|
|
|
|
> No.3258[元記事へ]
303
小さい桁を持つ倍数
参考サイト http://oeis.org/A181061
OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=0
FOR N=1 TO 100
LET T=F(N)
PRINT N; T !debug
LET S=S+T/N
NEXT N
PRINT S
END
EXTERNAL FUNCTION F(N) !f(n)
OPTION ARITHMETIC RATIONAL !多桁の整数
LET Y=1
DO
LET T=Y !3進法を利用する
LET X=0
LET K=1 !10^k
DO WHILE T>0
LET X=X+MOD(T,3)*K
LET T=INT(T/3)
LET K=K*10
LOOP
IF MOD(X,N)=0 THEN EXIT DO !題意を満たす
LET Y=Y+1
LOOP
LET F=X
END FUNCTION
EXTERNAL FUNCTION FF(N) !f(n)
OPTION ARITHMETIC RATIONAL !多桁の整数
LET X=N
DO
LET T=X !各桁の数字を確認する
DO WHILE T>0
IF MOD(T,10)>2 THEN EXIT DO !3以上なら、NG
LET T=INT(T/10)
LOOP
IF T=0 THEN EXIT DO !題意を満たす
LET X=X+N !次の倍数へ
LOOP
LET FF=X
END FUNCTION
倍数より、012の数を元に検索した方が速いようだ。
だが、9の倍数は大きな数になるので、N=10000はかなり手強い。
その２
OPTION ARITHMETIC RATIONAL !多桁の整数
LET t0=TIME
!PRINT f(999)
!PRINT USING "#####.##": TIME-T0
!STOP
LET N=100 !Σ
DIM FF(N) !f(n)
MAT FF=ZER
LET S=0
LET R=20 !10,15,20
DIM A(R) !並び ※重複順列を利用して、0,1,2の数を生成する
MAT A=CON !00…01
LET A(R)=2
LET C=N
DO
LET X=0 !f(n)の候補
FOR i=1 TO R !10進法の数とみなす
LET X=X*10+(A(i)-1)
NEXT i
FOR J=1 TO N
IF FF(J)=0 THEN !見つかっていない場合
IF MOD(X,J)=0 THEN !割り切れる
LET FF(J)=X
LET S=S+X/J
LET C=C-1 !残りの個数
END IF
END IF
NEXT J
IF C=0 THEN EXIT DO !すべてが見つかったなら
CALL NextReptPerm(A,3,R, rc) !次へ
IF rc<>0 THEN
PRINT "Rの値を大きくしてください。"; R
STOP
END IF
LOOP
PRINT S
PRINT USING "#####.##": TIME-T0
END
EXTERNAL FUNCTION F(N) !f(n)
OPTION ARITHMETIC RATIONAL !多桁の整数
LET R=20
DIM A(R) !並び ※重複順列を利用して、0,1,2の数を生成する
MAT A=CON !00…01
LET A(R)=2
DO
!!!MAT PRINT A; !debug
LET X=0 !f(n)の候補
FOR i=1 TO R !10進法の数とみなす
LET X=X*10+(A(i)-1)
NEXT i
IF MOD(X,N)=0 THEN EXIT DO !割り切れる
CALL NextReptPerm(A,3,R, rc) !次へ
IF rc<>0 THEN
PRINT "Rの値を大きくしてください。"; R
STOP
END IF
LOOP
LET F=X
END FUNCTION
EXTERNAL SUB NextReptPerm(A(),N,R, rc) !辞書式順序で次の順列を返す
OPTION ARITHMETIC RATIONAL !多桁の整数
LET rc=1 !完了
FOR i=R TO 1 STEP -1 !N進法R桁の数として ※インクリメント・カウンタ
IF A(i)<N THEN !1～Nで更新する
LET A(i)=A(i)+1
FOR j=i+1 TO R !A(i)=A(i+1)= … =A(R) 最初の並び
LET A(j)=1
NEXT j
LET rc=0 !未了
EXIT SUB
END IF
NEXT i
END SUB
|
|
|
|
投稿者：山中和義
投稿日：2013年12月28日(土)10時01分33秒
|
|
|
|
> No.3260[元記事へ]
291
Panaitopol素数
考察
x＞y＞0として、
p=(x^4-y^4)/(x^3+y^3)=(x-y)(x^2+y^2)/(x^2-xy+y^2)=(x-y)(x^2+y^2)/((x-y)^2+xy)
（終り）
OPTION ARITHMETIC RATIONAL !多桁の整数
LET C=0
FOR X=2 TO 10000 !X＞Y
FOR Y=1 TO X-1
LET P=(X-Y)*(X^2+Y^2)/(X^2-X*Y+Y^2)
IF P=INT(P) THEN
IF prmdiv(P)=P THEN !素数なら
LET C=C+1
PRINT X;Y;P !debug
END IF
END IF
NEXT Y
NEXT X
PRINT C;"通り"
END
!UBASICの整数論関連より UBASIC.LIB抜粋
EXTERNAL FUNCTION prmdiv(n) !１より大きな最小の約数
OPTION ARITHMETIC RATIONAL !多桁の整数
IF n<>INT(n) THEN !整数以外なら
PRINT "prmdiv関数でパラメータが不適当です。"
STOP
ELSEIF n=0 THEN
LET prmdiv=0
ELSE
LET n=ABS(n) !絶対値をとる
IF MOD(n,2)=0 THEN !２の倍数
LET prmdiv=2
ELSEIF MOD(n,3)=0 THEN !３の倍数
LET prmdiv=3
ELSE
FOR i=5 TO INTSQR(n) STEP 6
IF MOD(n,i)=0 THEN !5,11,17,23,29,…
LET prmdiv=i
EXIT FUNCTION
ELSEIF MOD(n,i+2)=0 THEN !7,13,19,25,31,…
LET prmdiv=i+2
EXIT FUNCTION
END IF !+1,+3,+5は２の倍数（偶数）、+1,+4は３の倍数、+5は５の倍数
NEXT i
LET prmdiv=n !その数自身
END IF
END IF
END FUNCTION
その２
考察
nを自然数とする。
x=(n+1)(n^2+n+1)、y=n(n^2+n+1)を与式に代入すると、
p=(x^4-y^4)/(x^3+y^3)=n^2+(n+1)^2
（終り）
OPTION ARITHMETIC RATIONAL !多桁の整数
LET C=0
LET N=1
DO
LET P=N^2+(N+1)^2
IF P>5E15 THEN EXIT DO
IF prmdiv(P)=P THEN !素数なら
LET C=C+1
PRINT N;P !debug
END IF
LET N=N+1
LOOP
PRINT C;"通り"
END
※サブルーチン部分は省略
|
|
|
|
投稿者：山中和義
投稿日：2013年12月28日(土)10時04分56秒
|
|
|
|
> No.3262[元記事へ]
221
アレクサンダー整数（Alexandrian integer）
参考サイト http://oeis.org/A147811
考察
1/A=1/p-1/q-1/r=(qr-rp-pq)/(pqr)、A=pqrより、1=qr-rp-pq ∴pq+1=(q-p)r
(q-p)を(pq+1)の約数とすると、r=(pq+1)/(q-p)
（終り）
OPTION ARITHMETIC RATIONAL !多桁の整数
LET t0=TIME
!!LET M=100 !A=1195116
LET M=5000 !A=82945319184
!!LET M=150000 !A=1884161251122450
DIM B(0 TO M+1) !※0,m+1は番兵
LET B(0)=0
LET C=0
!!FOR P=1 TO 106 !1195116^(1/3)より
FOR P=1 TO 4361 !82945319184^(1/3)より
!!FOR P=1 TO 123511 !1884161251122450^(1/3)=123511より
FOR Q=P+1 TO 2*P
LET R=(P*Q+1)/(Q-P)
IF R=INT(R) THEN !割り切れるなら
LET C=C+1 !※順不同
CALL ranking(P*Q*R, B,M,C) !並べ替える ※A=pqrは一般に増加する
END IF
NEXT Q
NEXT P
PRINT C;"通り"
PRINT B(1); B(M)
PRINT USING "#####.##": TIME-t0
END
EXTERNAL SUB ranking(X, A(),M,C) !昇順に並べる a[1]＜a[2]＜a[3]＜ …＜a[m]
OPTION ARITHMETIC RATIONAL !多桁の整数
LET P=C
IF C>M THEN LET P=M+1 !満タン
IF X<A(P-1) THEN
FOR i=P-1 TO 1 STEP -1 !右へスライドさせながら、挿入位置を見つける
IF A(i)<X THEN EXIT FOR
LET A(i+1)=A(i)
NEXT i
LET A(i+1)=X !挿入
ELSE
LET A(P)=X !最後に挿入する。
END IF
!!!PRINT X !debug
!!!MAT PRINT A;
END SUB
150000は無理みたい!
|
|
|
|
投稿者：山中和義
投稿日：2013年12月29日(日)10時15分7秒
|
|
|
|
> No.3263[元記事へ]
048
1^1+2^2+3^3+ … +1000^1000の最後の10桁を求めよ。
OPTION ARITHMETIC RATIONAL !多桁整数
LET S=0
FOR N=1 TO 1000
LET S=MOD(S+N^N,10^10)
NEXT N
PRINT S !9110846700
END
十進モードや2進モードでは、10^10どうしの2数のかけ算がオーバーフローすることを考慮する。
LET S=0
FOR N=1 TO 1000
LET S=MOD(S+pow(N,N,10^5),10^10)
NEXT N
PRINT S !9110846700
END
EXTERNAL FUNCTION mul(X,Y,B) !かけ算 xy mod b^2
LET X1=INT(X/B) !m進法へ
LET X0=MOD(X,B)
LET Y1=INT(Y/B)
LET Y0=MOD(Y,B)
!xy=(x1*b+x0)(y1*b+y0)=(x1*y1)*b^2+(x1*y0+x0*y1)*b+(x0*y0)より
LET mul=MOD((X1*Y0+X0*Y1)*B+X0*Y0,B*B)
END FUNCTION
EXTERNAL FUNCTION pow(A,K,B) !べき乗の計算 a^k mod b^2
LET P=1
LET X=A
DO WHILE K>0 !べき乗kを2進法展開する
IF MOD(K,2)=1 THEN LET P=mul(P,X,B) !p=p*x
LET X=mul(X,X,B) !x=x^2
LET K=INT(K/2)
LOOP
LET pow=P
END FUNCTION
|
|
|
|
投稿者：山中和義
投稿日：2013年12月29日(日)10時17分9秒
|
|
|
|
> No.3264[元記事へ]
018
最大経路の和 その1
考察
動的計画法による
(j-1)列 j列
(i-1)段 dp[i-1,j-1] dp[i-1,j]
＼ ↓
i段 MAX + a[i,j] → dp[i,j]
（終り）
!LET n=4 !最大値 23
!DATA 3
!DATA 7, 4
!DATA 2, 4, 6
!DATA 8, 5, 9, 3
LET n=15 !最大値 1074
DATA 75
DATA 95, 64
DATA 17, 47, 82
DATA 18, 35, 87, 10
DATA 20, 04, 82, 47, 65
DATA 19, 01, 23, 75, 03, 34
DATA 88, 02, 77, 73, 07, 63, 67
DATA 99, 65, 04, 28, 06, 16, 70, 92
DATA 41, 41, 26, 56, 83, 40, 80, 70, 33
DATA 41, 48, 72, 33, 47, 32, 37, 16, 94, 29
DATA 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14
DATA 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57
DATA 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48
DATA 63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31
DATA 04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23
DIM A(0 TO n-1, 0 TO n-1)
FOR i=0 TO n-1 !数値を読み込む
FOR j=0 TO i
READ A(i,j)
NEXT j
NEXT i
DIM DP(0 TO n-1, 0 TO n-1)
LET DP(0,0)=A(0,0)
FOR i=1 TO n-1 !i段目
LET DP(i,0)=DP(i-1,0) + A(i,0) !左端
FOR j=1 TO i-1 !j列目
LET DP(i,j)=MAX(DP(i-1,j-1),DP(i-1,j)) + A(i,j)
NEXT j
LET DP(i,i)=DP(i-1,i-1) + A(i,i) !右端
NEXT i
LET ans=0
FOR i=0 TO n-1
LET ans=MAX(ans,DP(n-1,i))
NEXT i
PRINT ans
END
|
|
|
|
投稿者：山中和義
投稿日：2014年 1月 1日(水)10時45分24秒
|
|
|
|
> No.3265[元記事へ]
148
パスカルの三角形の最初の10億列の要素で7で割り切れないものの数を答えよ。
考察
COMB(n,m)を直接計算すると、大きな数になっていく。
したがって、7の個数を数えることで、7の倍数を判定する。
n!の中のpの個数は、f(n,p)=[n/p]+[n/p^2]+[n/p^3]+ … である。
COMB(n,m)の中のpの個数は、
COMB(n,m)=n!/(m!(n-m)!)より、f(n,p)-(m,p)-f(n-m,p)
（終り）
OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=100 !10^9
LET S=1 !0段目 C(0,0)
FOR i=1 TO N-1 !i段目
LET M=i/2 !左端C(i,0)=1を除いた左側を検索する
LET S=S+2
FOR J=1 TO M
IF G(i,J,7)=0 THEN !7の個数が0なら、7で割り切れない
IF J<M THEN LET S=S+2 ELSE LET S=S+1 !対称性による
END IF
NEXT J
NEXT i
PRINT S; N*(N+1)/2-S
END
EXTERNAL FUNCTION F(N,P) !n!の中のpの個数 f(n)=[n/p]+[n/p^2]+[n/p^3]+ …
OPTION ARITHMETIC RATIONAL !多桁の整数
LET W=0
LET T=N
DO
LET T=INT(T/P)
LET W=W+T
LOOP WHILE T>0
LET F=W
END FUNCTION
EXTERNAL FUNCTION G(N,M,P) !COMB(n,m)の中のpの個数
OPTION ARITHMETIC RATIONAL !多桁の整数
LET G=F(N,P)-F(M,P)-F(N-M,P)
END FUNCTION
たが、Nが大きな場合は計算が困難である。
実際に、COMB(n,m)の中の7の個数の分布を表すと次のようになる。
1: 0
2: 0 0
3: 0 0 0
4: 0 0 0 0
5: 0 0 0 0 0
6: 0 0 0 0 0 0
7: 0 0 0 0 0 0 0
8: 0 1 1 1 1 1 1 0
9: 0 0 1 1 1 1 1 0 0
10: 0 0 0 1 1 1 1 0 0 0
11: 0 0 0 0 1 1 1 0 0 0 0
12: 0 0 0 0 0 1 1 0 0 0 0 0
13: 0 0 0 0 0 0 1 0 0 0 0 0 0
14: 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15: 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0
16: 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0
17: 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0
18: 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0
19: 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0
20: 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
21: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22: 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0
23: 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0
24: 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0
25: 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0
26: 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0
27: 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
28: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
29: 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0
30: 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0
31: 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0
32: 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0
33: 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0
34: 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
35: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
36: 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0
37: 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0
38: 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0
39: 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0
40: 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0
41: 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
42: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
43: 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0
44: 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0
45: 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0
46: 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0
47: 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0
48: 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
49: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
三角形の形状で規則正しく分布している。これを利用して、
OPTION ARITHMETIC RATIONAL !多桁整数
DEF T(N)=N*(N+1)/2
LET N=10^9
DIM S(0 TO 7-1)
FOR i=0 TO 7-1
LET S(i)=T(i)
NEXT i
LET C=0
LET X=1
DO WHILE N>0 !7進法へ
LET R=MOD(N,7)
LET C=C*(R+1) + S(R)*X
LET X=X*28 !X*T(7)
LET N=INT(N/7)
LOOP
PRINT C !2129970655314432
END
|
|
|
|
投稿者：山中和義
投稿日：2014年 1月 1日(水)11時00分46秒
|
|
|
|
> No.3274[元記事へ]
160
任意のNに対して、f(N)をN!の末尾の0の前にある最後の5桁とする。
f(1,000,000,000,000)を求めよ。
LET S=1
FOR N=2 TO 10^12
LET T=N
DO WHILE MOD(T,5)=0 !2*5=10で割る
LET S=S/2
LET T=INT(T/5)
LOOP
LET S=MOD(S*T,10^5)
NEXT N
PRINT S
END
これが処理可能なら良いのだが、、、
最後の5桁、すなわち10^5での数理があるようだ。
考察
g(n)は、nまでの5で割り切れる数を除いて、かつ 2の因子を5つまで取り除いた積とする。
g(n*10^5)=g(10^5)^n≡9376 mod 10^5
9376^k≡9376 mod 10^5
（終り）
!!OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=10^12 !n!
LET M=10^5
!PRINT G(2*10^5), modpow(G(10^5),2,M) !debug
PUBLIC NUMERIC E !2^e
LET E=0
LET W=1
LET T=N
DO WHILE T>0
IF MOD(T,M)=0 THEN !g(n*10^5)の場合
PRINT T;"+" !debug
LET W=MOD(W*9376,M)
ELSE
PRINT T !debug
IF N0=0 THEN LET N0=T
LET W=MOD(W*G(T),M)
END IF
LET T=INT(T/5)
LOOP
PRINT MOD(W*modpow(2,E-F(N0,5),M), M) !16576
END
EXTERNAL FUNCTION F(N,P) !n!の中のpの個数 f(n)=[n/p]+[n/p^2]+[n/p^3]+ …
!!OPTION ARITHMETIC RATIONAL !多桁の整数
LET W=0
LET T=N
DO
LET T=INT(T/P)
LET W=W+T
LOOP WHILE T>0
LET F=W
END FUNCTION
EXTERNAL FUNCTION G(N) !nまでの5で割り切れる数を除いて、かつ 2の因子を5つまで取り除いた積
!!OPTION ARITHMETIC RATIONAL !多桁の整数
LET T=1
FOR i=2 TO N
IF MOD(i,5)=0 THEN !55で割り切れる数を除く
ELSE
LET W=i
FOR J=1 TO 5 !2の因子を5つまで取り除く
IF MOD(W,2)=0 THEN !2^e
LET W=W/2
LET E=E+1
END IF
NEXT J
LET T=MOD(T*W,10^5) !積
END IF
NEXT i
LET G=T
END FUNCTION
!UBASICの整数論関連より UBASIC.LIB抜粋
EXTERNAL FUNCTION modpow(a,n,b) !a^n≡x mod b のxを返す ※nは非負整数
!!OPTION ARITHMETIC RATIONAL !多桁の整数
IF n<0 OR n<>INT(n) THEN !非負整数以外なら
PRINT "modpow関数でパラメータが不適当です。"; a;n;b
STOP
ELSE
LET S=MOD(1,b)
DO WHILE n>0 !べき乗nを２進展開する
IF MOD(n,2)=1 THEN LET S=MOD(S*a,b) !ビットが１なら計算する
LET a=MOD(a*a,b)
LET n=INT(n/2)
LOOP
LET modpow=S
END IF
END FUNCTION
|
|
|
|
投稿者：山中和義
投稿日：2014年 3月19日(水)19時13分50秒
|
|
|
|
> No.3275[元記事へ]
029
2≦a≦100と2≦b≦100を満たす整数a,bについて、a^bを全て考えてみよう。
いくつの異なる値が存在するか。
考察
2≦a≦A、2≦b≦Bとして、kはa^k≦Aを満たす最大の整数とする。
k個の数からなる組{a, a^2, a^3, …, a^k}を考える。
例
A=B=10のとき
{2, 2^2=4, 2^3=8}、{3, 3^2=9}、{5}、{6}、{7}、{10}
a=2,3,5,6,7,10,11,12,13,…,[√A] のとき、k≧2
a＞[√A] のとき、k=1
各要素のべき乗は、重複する数を生成する。
例
a=2のとき
| 2 3 4 5 … B
----+-----------------------------------------------------
2^1 | 2^2 2^3 2^4 2^5 … 2^B
2^2 | (2^2)^2 (2^2)^3 (2^2)^4 (2^2)^5 … (2^2)^B
2^3 | (2^3)^2 (2^3)^3 (2^3)^4 (2^3)^5 … (2^3)^B
：
2^k | (2^k)^2 (2^k)^3 (2^k)^4 (2^k)^5 … (2^k)^B
べき乗の部分に着目すると、
| 2 3 4 5 … B
----+-------------------------------
2^1 | 2 3 4 5 … B
2^2 | 4 6 8 10 … 2B
2^3 | 6 9 12 15 … 3B
：
2^k | 2k 3k 4k 5k … kB
同じ数字の箇所は同じ数になるので、重複する数となる。
また、重複する個数はkとBに依存する。
（終り）
例
2≦a≦10、2≦b≦10のとき、2^k≦10から、k=1,2,3
積算表
k＼b | 2 3 4 5 6 7 8 9 10
-----+-----------------------------
1 | 2 3 4 5 6 7 8 9 10
2 | 4 6 8 10 12 14 16 18 20
3 | 6 9 12 15 18 21 24 27 30
より、
重複を除いた個数をG(k)とすると、
G(1)=9通り、G(2)=14通り、G(3)=19通り
a={2,2^2,2^4},{3,3^2},5,6,7,10より、
a=2のとき、G(3)通り
a=3のとき、G(2)通り
a=5,6,7,10のとき、G(1)通り
なので、
19*1+14*1+9*4=69通り
（終り）
!Project Euler Problem（プロジェクトオイラー） 029
LET A=100
LET B=100
LET M=0 !組のなかで数の個数が最大のもの
LET T=A
DO WHILE T>0
LET M=M+1
LET T=INT(T/2) !{2, 2^2, 2^3, …, 2^m}
LOOP
LET M=M-1
PRINT "M="; M !debug
!乗算表
! 2 3 4 … x … q … B
! 1:
! 2:
! ：
! p: pq=n
! ：
! k-1: (k-1)B
! k: → → kx=n → →
! ：
! m:
!をつくって、G(k)を求める。
DIM G(M) !重複を除いた個数をG(k)とする
LET G(1)=B-1 !1段目
LET C=G(1)
FOR K=2 TO M !k段目
LET T=INT((K-1)*B/K) !kxが(k-1)Bより大きな数はすべて重複しない
FOR X=2 TO T !b列目
LET N=K*X
FOR P=1 TO K-1 !nをpqに分解する
LET Q=N/P
IF Q=INT(Q) AND (Q>=2 AND Q<=B) THEN EXIT FOR !重複する
NEXT P
IF P>K-1 THEN LET C=C+1 !重複しないなら
NEXT X
LET C=C+(B-T)
LET G(K)=C
NEXT K
MAT PRINT G; !debug
!組（A=2,3,5,6,7,10,11,12,13,…）に応じて計算していく。
LET C=0
LET AA=INT(SQR(A))
DIM F(AA) !2～[√A]までの数（篩いに用いる）
MAT F=ZER
LET S=0 !組にすることで除外された数の個数
FOR J=2 TO AA !素因数分解して、因数の組み合わせで組に分ける
IF F(J)=0 THEN !新しい組なら
PRINT "A="; J !debug
LET K=0
LET T=J !{j^1, j^2, j^3, …, j^k}の要素は、k個
DO WHILE T<=A
IF T<=AA THEN LET F(T)=1 !同じ組である
LET S=S+1
LET K=K+1
LET T=T*J !次へ
LOOP
PRINT K !debug
LET C=C+G(K)
END IF
NEXT J
LET C=C+(A-1-S)*G(1) !√Aより大きいものは、(B-1)通り
PRINT C; "通り" !9183
END
実行結果
M= 6
99 149 199 240 291 328
A= 2
6
A= 3
4
A= 5
2
A= 6
2
A= 7
2
A= 10
2
9183 通り
|
|
|
|
投稿者：山中和義
投稿日：2014年 3月22日(土)09時30分5秒
|
|
|
|
> No.3340[元記事へ]
045
40755は、三角数かつ五角数かつ六角数である。
次の三角数かつ五角数かつ六角数となる数を求めよ。
3つの数を競い合わせる方法
!!OPTION ARITHMETIC RATIONAL !多桁の整数
DEF T(N)=N*(N+1)/2 !三角数
DEF P(N)=N*(3*N-1)/2 !五角数
DEF H(N)=N*(2*N-1) !六角数
LET N1=1
LET N2=1
LET N3=1
FOR K=1 TO 3 !1番目、2番目、3番目
LET A=T(N1)
LET B=P(N2)
LET C=H(N3)
DO UNTIL A=B AND B=C
LET M=MAX(MAX(A,B),C) !一番大きな数に揃える
DO WHILE A<M
LET N1=N1+1
LET A=T(N1)
LOOP
DO WHILE B<M
LET N2=N2+1
LET B=P(N2)
LOOP
DO WHILE C<M
LET N3=N3+1
LET C=H(N3)
LOOP
LOOP
PRINT STR$(K);":"; A; N1;N2;N3 !1533776805
LET N1=N1+1 !次へ
LET N2=N2+1
LET N3=N3+1
NEXT K
END
2次方程式を解く方法
!!OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=1
FOR K=1 TO 3 !1番目、2番目、3番目
DO
LET X=N*(2*N-1) !六角数
LET D=SQR(1+24*X) !五角数X=N(3N-1)/2より
IF D=INT(D) THEN
LET M=(1+D)/6
IF M=INT(M) THEN
LET D=SQR(1+8*X) !三角数X=N(N+1)/2より
IF D=INT(D) THEN
LET M=(1+D)/2
IF M=INT(M) THEN EXIT DO
END IF
END IF
END IF
LET N=N+1
LOOP
PRINT STR$(K);":"; X ;N !1533776805
LET N=N+1
NEXT K
END
|
|
|
戻る