|
#include <stdio.h>
#include <string.h>
#define MAX 72 /* 扱う桁数の最大値 */
#define N ((MAX-1)/4+1) /* MAX桁を記憶するための配列サイズ */
/* プロトタイプ宣言 */
void input_num(int D[],int); /* 整数をキーボードから入力すると
４桁ずつ区切って配列D[]に記憶する */
void display(int D[]); /* 配列 D[] に記憶している数を表示 */
/*↓割り算.第3引数に商が多倍長で返る.第1引数と第3引数が同じ配列でもok.割り切れるなら真を返す*/
int div(int [],int [],int []);
void koubaisu(int A[],int B[],int C[]);
void mult(int A[], int B[], int C[]);
void sub(int A[], int B[], int C[]);
void hiku(int A[], int B[], int C[]);
int comp(int A[], int B[]);
void hiku2(int A[], int B[]);
int main(void) {
/* 大きな整数を記憶する配列 */
int A[N], B[N], C[N];
int j=1,i;
input_num(A,j++);
input_num(B,j);
koubaisu(A,B,C);
printf("\n 最大公約数は"); display(C);
return(0);
}
void koubaisu(int A[],int B[],int C[]){
int i,a1[N],a2[N],b1[N],b2[N],D[N];
int *Ap1,*Ap2,*Bp1,*Bp2,*buf;
Ap1 = a1,Ap2 = a2;
Bp1 = b1,Bp2 = b2;
for(i = 0;i < N;i++){
Ap1[i] = A[i];
Bp1[i] = B[i];
D[i] = C[i] = 0;
}
C[0] = 1;
for(D[0] = 2;!div(Ap1,D,Ap2) && !div(Bp1,D,Bp2);){
buf = Ap1,Ap1 = Ap2,Ap2 = buf;
buf = Bp1,Bp1 = Bp2,Bp2 = buf;
mult(C,D,C);
}
for(D[0] = 3;comp(Bp1,D);){
while(!div(Ap1,D,Ap2) && !div(Bp1,D,Bp2)){
buf = Ap1,Ap1 = Ap2,Ap2 = buf;
buf = Bp1,Bp1 = Bp2,Bp2 = buf;
mult(C,D,C);
printf("現在計算中,今");
display(D);
printf("で割り終わりました。今のとこ公倍数は");
display(C);
printf("\n");
}
for(D[i=0]+= 2;D[i] >=10000 && i < N-1;){//桁上げ
D[i] -=10000;
D[++i]++;
}
}
}
int div(int A[],int B[],int C[]){
int i;
int D[N];
for(i = 0;i < N;i++){
D[i] = A[i];
C[i] = 0;
}
for(i = 0;comp(D,B);i++){
hiku2(D,B);
for(C[i=0]++;D[i] >=10000 && i < N-1;){//桁上げ
C[i] -=10000;
C[++i]++;
}
}
for(i = 0;i < N;i++){
if(D[i]){
return 1;
}
}
return 0;
}
void tasu(int A[], int B[]){
int i,carry=0;
for(i=0;i < N-1;i++){
A[i] += B[i]+carry;
carry = A[i] >= 10000;
if(carry){
A[i] -=10000;
}
}
}
void mult(int A[], int B[], int C[]){
int i;
int D[N],E[N];
for(i = 0;i < N;i++){
D[i] = A[i];
E[i] = C[i] = 0;
}
E[0]=1;
while(comp(B,E)){
tasu(C,D);
for(E[i=0]++;E[i] >=10000 && i < N-1;){//桁上げ
E[i] -=10000;
E[++i]++;
}
}
}
void hiku(int A[], int B[], int C[]) {
int i, carry;
/* 配列 C の初期化 */
for (i=0; i<=N-1; i++) {
C[i]=0;
}
/* A-B を C に記録 */
for (i=0, carry=0; i<=N/2-1; i++) {
C[i] = A[i] - B[i] - carry;
carry = C[i] < 0;
if (carry) C[i] += 10000;
}
}
void hiku2(int A[], int B[]) {
int i, carry;
for (i=0, carry=0; i<=N/2-1; i++) {
A[i] = A[i] - B[i] - carry;
carry = A[i] < 0;
if (carry) A[i] += 10000;
}
}
int comp(int A[], int B[]) {
int i;
for(i=N/2;i>=0;i--){
if(A[i]>B[i]){
return(1);
}
else if(A[i]<B[i]){
return(0);
}
}
return 1;
}
/* 整数をキーボードから入力すると４桁ずつ区切って配列D[]に記憶する関数 */
void input_num(int D[],int j) {
char line[MAX];
int last;
int i,digit;
printf(" 整数%d:%d 桁以下の整数を入力して下さい：",j, MAX/2);
fgets(line, sizeof(line), stdin);
for (i=0; i<=N-1; i++) {
D[i] = 0;
}
last= strlen(line)-2; /* １の桁のindex */
for (i=0; last >=0; i++) {
for (digit=1; digit<=1000 && last>=0; digit*=10, last--) {
D[i] += (line[last]-'0')*digit;
}
}
return;
}
/* 配列 D[] に記憶している数を表示 */
void display(int D[]) {
int i,digit,temp,flag=1;
/* digit は桁数、temp は表示されていない部分 */
for (i=N-1; i>0; i--) {
if (D[i]!=0) break;
}
printf("%04d",D[i]);
for (i-- ; i>=0; i--) {
for(digit=1000, temp=D[i]; digit>=1; digit/=10) {
printf("%d", temp/digit); /* digit で割った商を表示 */
temp%=digit; /* digit で割った余りに置き換え */
}
}
return;
}
|
