|
投稿者：山中和義
投稿日：2014年 4月 4日(金)10時55分19秒
|
|
|
|
問題
3で割って2余り、5で割って3余り、7で割って5余り、11で割って7余る4桁の自然数はいくつあるか。
答え
3で割ると2余るので、1を加えると3の倍数となる。
5で割ると3余るので、2を加えると5の倍数となる。
7で割ると5余るので、2を加えると7の倍数となる。
11で割ると7余るので、4を加えると11の倍数となる。
これに着目して、
3,5,7,11の最小公倍数は、3×5×7×11=1155である。
と
+3: 1 4 7 10 13 16 19 22 25 28 31 34 37
+5: 2 7 12 17 22 27 32 37
+7: 2 9 16 23 30 37
+11: 4 15 26 37
より、
題意を満たす数は、1155-37=1118
残りは1155を加えていくと、
1118+1155=2273
2273+1155=3428
3428+1155=4583
4583+1155=5738
5738+1155=6893
6893+1155=8048
8048+1155=9203
したがって、8個となる。
（終り）
求める数が、0と最小公倍数のどちらに近いかで検索する回数が多くなったり少なかったりする。
次の例では真ん中あたりにあるので、どちらでも同じとなる。
問題
3で割って2余り、5で割って3余る2桁の整数はいくつあるか。
プラス方向
+3: 2 5 8
+5: 3 8
マイナス方向
+3: 1 4 7
+5: 2 7
1118を見つける方法
別解
7×11×13=1001より、11で割って7余る4桁の数で最小となるのは、1001+7=1008
5の倍数は一の位が0,5（5の倍数の判定）なので、5で割って3余るのは、3,8である。
これに注意して（5,3,7の倍数の順に絞り込みながら）、
まず、1008は、1+0+0+8=9（3の倍数の判定）なので、3で割リ切れる。題意を満たさない。
11×5=55なので、次は、1008+55=1063
これは、1+0+6+3=10なので、3で割って1余る。題意を満たさない。
続けて、1063+55=1118
これは、1+1+1+8=11 なので、3で割って2余る。
また、1118÷7=159余り5 なので、7で割って5余る。
以上より、題意を満たす4桁の数の最小は、1118である。
（終り）
算数やパズルとしてアプローチしてみたが、一般に、次のように解くことができる。
!連立1次合同式を解く
OPTION ARITHMETIC RATIONAL !多桁の整数
DATA 4
DATA 3,2 !3で割ると2余る
DATA 5,3 !5で割ると3余る
DATA 7,5 !7で割ると5余る
DATA 11,7 !11で割ると7余る
DATA 1000,10000 !1000以上10000未満の範囲
READ K
DIM A(K),B(K) !x≡a mod b
FOR i=1 TO K
READ B(i),A(i)
NEXT i
LET S=1 !中国剰余定理（Chinese remainder theorem）より
FOR i=1 TO K
LET S=S*B(i) !b1*b2* … *bn
NEXT i
!!!PRINT S !debug
LET R=0 !x=Σui*xi*ai (mod b1*b2* … *bn)
FOR i=1 TO K
LET T=S/B(i) !ui*xi≡1 (mod bi)
LET R=R+T*modinv(T,B(i))*A(i)
NEXT i
LET R=MOD(R,S) !解
!!!PRINT R !debug
READ P,Q ![p,q)の範囲で検索する
LET C=0
LET N=CEIL((P-R)/S)*S+R
DO WHILE N<Q
LET C=C+1
PRINT N
LET N=N+S
LOOP
PRINT C; "個"
!初項r、公差sの等差数列 項数k個 r,r+s,r+2s,…,r+(k-1)s
PRINT CEIL((Q-R)/S)-CEIL((P-R)/S); "個"
END
!UBASIC.LIB 抜粋
EXTERNAL FUNCTION modinv(a,n) !nを法としたaの逆元 a*x≡1 (mod n)
OPTION ARITHMETIC RATIONAL !多桁の整数
LET d0=a !(a,1)
LET x0=1
LET d1=n !(n,0)
LET x1=0
DO WHILE d1<>0 !拡張ユークリッドの互除法によりa*x+b*y=cの解を求める
LET t=INT(d0/d1)
LET T1=d0 !(d0,x0)=(d1,x1)、(d1,x1)=(d0-t*d1,x0-t*x1)
LET T2=x0
LET d0=d1 !次へ
LET x0=x1
LET d1=T1-t*d1
LET x1=T2-t*x1
LOOP
IF d0=1 THEN !GCD(a,n)=1なら
IF x0<0 THEN LET x0=x0+n !mod(x0,n)
LET modinv=x0
ELSE
LET modinv=0
END IF
END FUNCTION
|
|
|
|
投稿者：GAI
投稿日：2014年 4月 5日(土)10時46分20秒
|
|
|
|
> No.3353[元記事へ]
山中和義さんへのお返事です。
> 問題
> 3で割って1余り、4で割って2余り、5で割って3余り、8で割って4余る4桁の自然数はいくつあるか。
題意を満たす数は、存在しない。
従って 0個
であるはずなのですが
次のプログラムで実行してみたら
>
> !連立1次合同式を解く
>
> OPTION ARITHMETIC RATIONAL !多桁の整数
>
> DATA 4
> DATA 3,1 !3で割ると1余る
> DATA 4,2 !4で割ると2余る
> DATA 5,3 !5で割ると3余る
> DATA 8,4 !8で割ると4余る
> DATA 1000,10000 !1000以上10000未満の範囲
>
> READ K
> DIM A(K),B(K) !x≡a mod b
> FOR i=1 TO K
> READ B(i),A(i)
> NEXT i
>
>
> LET S=1 !中国剰余定理（Chinese remainder theorem）より
> FOR i=1 TO K
> LET S=S*B(i) !b1*b2* … *bn
> NEXT i
> !!!PRINT S !debug
>
> LET R=0 !x=Σui*xi*ai (mod b1*b2* … *bn)
> FOR i=1 TO K
> LET T=S/B(i) !ui*xi≡1 (mod bi)
> LET R=R+T*modinv(T,B(i))*A(i)
> NEXT i
> LET R=MOD(R,S) !解
> !!!PRINT R !debug
>
>
> READ P,Q ![p,q)の範囲で検索する
> LET C=0
> LET N=CEIL((P-R)/S)*S+R
> DO WHILE N<Q
> LET C=C+1
> PRINT N
> LET N=N+S
> LOOP
> PRINT C; "個"
>
>
> !初項r、公差sの等差数列 項数k個 r,r+s,r+2s,…,r+(k-1)s
> PRINT CEIL((Q-R)/S)-CEIL((P-R)/S); "個"
>
> END
>
>
> !UBASIC.LIB 抜粋
>
> EXTERNAL FUNCTION modinv(a,n) !nを法としたaの逆元 a*x≡1 (mod n)
> OPTION ARITHMETIC RATIONAL !多桁の整数
> LET d0=a !(a,1)
> LET x0=1
> LET d1=n !(n,0)
> LET x1=0
> DO WHILE d1<>0 !拡張ユークリッドの互除法によりa*x+b*y=cの解を求める
> LET t=INT(d0/d1)
> LET T1=d0 !(d0,x0)=(d1,x1)、(d1,x1)=(d0-t*d1,x0-t*x1)
> LET T2=x0
> LET d0=d1 !次へ
> LET x0=x1
> LET d1=T1-t*d1
> LET x1=T2-t*x1
> LOOP
> IF d0=1 THEN !GCD(a,n)=1なら
> IF x0<0 THEN LET x0=x0+n !mod(x0,n)
> LET modinv=x0
> ELSE
> LET modinv=0
> END IF
> END FUNCTION
>
>
実行結果
1408
1888
2368
2848
3328
3808
4288
4768
5248
5728
6208
6688
7168
7648
8128
8608
9088
9568
18 個
18 個
で明らかに1408は条件を満たしません。？
|
|
|
|
投稿者：山中和義
投稿日：2014年 4月30日(水)19時27分36秒
|
|
|
|
問題
1000個近いキャンディを子供達へ、
7個ずつ配ると4個余り、5個ずつ配ると3個余り、3個ずつにすると2個余ったという。
最初にキャンディは何個あったのか？
答え
1000÷3の余りを求める。3の倍数の判定から、1
1000÷5の余りを求める。5の倍数の判定から、0
1000÷7の余りを求める。筆算で求めて、6
___142_
7 ) 1000
_7_
30
_28_
20
_14_
6
または、1001=7×11×13より、6 ※受験なれしている
1000個のとき、分配状況を図示すると、
③………③③○
⑤……⑤⑤
⑦…⑦⑦○○○○○○
題意を満たさない。
そこで1つ増やしてみると、
1001個のとき、
③………③③ ○○
⑤……⑤⑤ ○
⑦…⑦⑦⑦
題意を満たさない。
そこで1つ減らしてみると、
999個のとき、
③………③③
⑤……⑤ ○○○○
⑦…⑦⑦○○○○○
同様に、±2,±3,±4,…を考える。
1002個のとき、
③………③③③
⑤……⑤⑤ ○○
⑦…⑦⑦⑦○
題意を満たさない。
998個のとき、
③………③ ○○
⑤……⑤ ○○○
⑦…⑦⑦○○○○
題意を満たす。
（終り）
●中学生向け（後半部分）
余りの規則性より、
個数 3 5 7
-----------
998 2 3 4 ← 答え
999 0 4 5
1000 1 0 6
1001 2 1 0
1002 0 2 1
を得る。
LET N=1000
FOR K=0 TO N !n±k
FOR S=1 TO -1 STEP -2 !符号
LET M=N+S*K
IF MOD(M,7)=4 THEN !題意を満たすなら
IF MOD(M,5)=3 THEN
IF MOD(M,3)=2 THEN
PRINT M
STOP
END IF
END IF
END IF
NEXT S
NEXT K
END
実行結果
998
|
|
|
戻る