yukicoder No.415 ぴょん

問題はこちら
No.415 ぴょん - yukicoder

indexを1ずらして0-basedとする
一度スタートすると同じ方向に進み続けるしかないのでi回目の移動先はi*D%N
よって求めるべきはi*D%Nが0となる最小の非負整数iから1引いたもの（実際に移動できる回数なので）
即ちi*D=LCM(N,D)となりi=LCM(N,D)/D
ここで一般に二つの正整数A,Bに対しGCD(A,B)*LCM(A,B)=A*Bであることからi=N/GCD(N,D)を得る
あとは互除法するだけ

int gcd(p,q){return q?gcd(q,p%q):p;}
int main(){
	int n,d;
	scanf("%d%d",&n,&d);
	printf("%d",n/gcd(n,d)-1);
	return 0;
}

ぎゅ

s,t;
main(n,d){
	for(scanf("%d%d",&n,&d),s=n;t=d;n=t)d=n%d;
	s=!printf("%d",s/n-1);
}

79B