AOJ_0113 Period
PCKに参加することになったので練習しています。
まだまだ先ですけどね
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0113
解法
筆算をするようにやっていく。
余りを配列に記憶しておいて、
以前と同じ余りが存在している⇔循環している
を利用する。
実装が大変かと思ったがそれほどでもなかった。
#include <cstdio> #include <algorithm> using namespace std; char r[100]; //商 int s[100]; //あまりを入れていく int main(){ int p, q; while(scanf("%d %d", &p, &q) != EOF){ // p/qの小数部分 p = p % q; s[0] = p; int x = -1, y = -1; for(int i = 0; ; i++){ int a = (s[i] * 10) % q; r[i] = (s[i] * 10 / q) + '0'; s[i + 1] = a; if(a == 0){ //割りきれた r[i + 1] = 0; break; } //循環しているか判定(同じあまりがあるか) for(int j = 0; j < i; j++){ if(s[j] == s[i + 1]){ if(j + 1 == i) i--; x = j; y = i + 1; r[i + 1] = 0; goto show; } } } show: printf("%s\n", r); if(x != -1){ for(int i = 0; i < x; i++){ printf(" "); } for(int i = x; i < y; i++){ printf("^"); } puts(""); } } return 0; }