a240 - 第一題：1 / 17 小數第 n 位

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算 1/17 的小數表示中，小數點後第 n 位數字，以及小數點後第 1 位到第 n 位數字的和。

解題思路

由於 1/17 是循環小數，我們可以先計算出 1/17 的循環節。透過長除法可以發現 1/17 的循環節長度為 16。程式碼中 A 陣列儲存了循環節中每個位置的數字，B 陣列儲存了每個位置的數字值。程式利用模數運算 a % 16 找到對應的數字，並利用 a / 16 計算數字和。

複雜度分析

• 時間複雜度: O(t) 其中 t 是測試案例的數量。
• 空間複雜度: O(1)

程式碼

#include <stdio.h>
int main(){
	int a,n;
	int A[16]={0,0,5,13,21,23,26,31,33,42,46,47,48,55,61,65},B[16]={7,0,5,8,8,2,3,5,2,9,4,1,1,7,6,4};
	scanf("%d",&n);
	while(n--){
		scanf("%d",&a);
		printf("%d %d\n",B[a%16],(a/16)*72+A[a%16]);
	}
}