|
|
問題
10^5以下の正の整数のうち、
3, 5, 7, 11, 13, 17, 19, 23, 29, 31
の少なくともどれか一つの倍数となるものの総和を求めてください。
答え
3469796305
範囲が小さい場合、ふるい用の配列を設けることができる。
OPTION ARITHMETIC RATIONAL
DATA 3,5,7,11,13,17,19,23,29,31,-1
LET N=10^5
DIM F(0 TO N) !篩い
MAT F=ZER
DO
READ A
IF A<0 THEN EXIT DO
FOR K=0 TO N STEP A !その倍数
LET F(K)=1
NEXT K
LOOP
LET S=0 !和
FOR K=1 TO N
IF F(K)>0 THEN LET S=S+K
NEXT K
PRINT S
END
その2
考察
20以下、3,5の倍数とする。
3の倍数は3,6,9,12,15,18なので、和は(3+18)×6÷2=63
5の倍数は5,10,15,20なので、和は(5+20)×4÷2=50
3×5=15の倍数は15なので、和は15
これより、63+50-15=98
（終り）
OPTION ARITHMETIC RATIONAL
LET N=10^5
DATA 3,5,7,11,13,17,19,23,29,31 !互いに素
DIM P(10)
MAT READ P
LET S=0 !和
FOR C=1 TO 2^UBOUND(P)-1 !組み合わせ（ビットパターン）
LET T=C
LET X=0 !1の個数
LET D=1
FOR B=1 TO UBOUND(P) !ビット位置
IF T=0 THEN EXIT FOR
IF MOD(T,2)=1 THEN
LET X=X+1
LET D=D*P(B)
END IF
LET T=INT(T/2) !次へ
NEXT B
LET K=INT(N/D) !項数 k
LET W=K*(K+1)*D/2 !和 d+2d+3d+ … +kd、kd≦n
!集合A,B,Cなら、個数 n(A∪B∪C)=n(A)+n(B)+n(C)-n(A∩B)-n(B∩C)-n(C∩A)+n(A∩B∩C) より
IF MOD(X,2)=1 THEN LET S=S+W ELSE LET S=S-W
NEXT C
PRINT S
END
|
|