fork download
copy 
  1. #include <stdio.h>
  2. #include <math.h> //sqrt()
  3.  
  4. /*
  5. 値nが与えられたときに次の条件を満たす数a,bを求め表示するプログラム
  6. 　aとbの最小公倍数がn
  7.   a<bかつ(b-a)が最小
  8. */
  9. void solve(int);
  10. int gcm(int , int);
  11.  
  12.  
  13. int main(){
  14. //printf("[main]called\n\n");
  15. 	solve(       360); 
  16. 	solve(      1000);
  17. 	solve(      3000);
  18. 	solve(      5040);
  19. 	solve(      5400);
  20. 	solve(      9000);
  21. 	solve(1088391168);
  22. 	solve(1338557220);
  23. 	solve(1000009961);
  24. 	solve(2000019922);
  25. 	solve( 357912991);
  26. 	solve(2147477946);
  27. 	solve(2147483646);
  28. 	solve(2147483629);
  29. 	solve(  13693680);
  30. 	solve( 232792560);
  31. 	solve(2095502089);
  32. 	solve(2082117833);
  33. }
  34.  
  35. void solve(int n){
  36. //printf("[solve]called\n");
  37. 	printf("n = %d → ",n);
  38. 	// nが1の場合はn=a=b=1となり解なし
  39. 	if (n <= 1){
  40. 		printf("no answer\n");
  41. 		return ;
  42. 	}
  43. 	/*
  44. 	aとbを求めるにあたり、以下の値を仮定する
  45. 	　k :aとbの最大公約数　nの約数のいずれか
  46. 	　l :n/k
  47. 	　la:a/kとなる数
  48. 	　lb:b/kとなる数
  49. 	　　la*lb=l、laとlbの最大公約数は1となる
  50. 	　min_d:k*(lb-la)の最小値
  51. 	*/
  52. 	int a = 0 , b = 0 ;
  53. 	int k , l , la , lb;
  54. 	int min_d = n; //仮にnを設定。実際にはk=1,la=1,lb=nの時に最大となり必ず(n-1)以下の値で更新される
  55.  
  56. 	//k=1(aとbの最大公約数1)を計算する
  57. //printf("@k = 1\n");
  58. 	k = 1;
  59. 	l = n;
  60. 	//laを√l(小数点以下切捨て)に設定
  61. 	la = (int)sqrt(l);
  62. 	//lが平方数(la^2=l)ならlaを-1する
  63. 	if(la*la == l){
  64. 		la--;
  65. 	}
  66. 	do {
  67. //printf("k=%d l=%d la=%d \n",k,l,la);
  68. 		//laがlの約数ではない場合はスキップする
  69. 		if((l % la) == 0 ){
  70. 			lb = l / la;  //lbを設定
  71. 			//laとlbの最大公約数が1でなければスキップ
  72. 			if (gcm(la,lb) == 1){
  73. 				//(lb-la)*1(k)がmin_dを下回るならa,b,min_dの更新を行いループから抜ける
  74. 				if ((lb - la)<= min_d) {
  75. //printf("k=%d l=%d la=%d lb=%d\n",k,l,la,lb);
  76. 					a = k * la ;
  77. 					b = k * lb ;
  78. 					min_d = (lb - la)*k;
  79. 					break ;
  80. 				}
  81. 			}
  82. 		}
  83. 		la-- ; //laを減らす
  84. 	}while(la >= 1); //laの最小値は1
  85.  
  86. 	//kが2以上の場合を計算する。カウンタとしてiを使用
  87. 	int i = 2;
  88. 	do {
  89. 		//iがnの約数でない場合はスキップする
  90. 		if ((n % i) == 0) {
  91. 			//k = i と k = n / i の２つの場合をそれぞれ計算する
  92. 			k = i;
  93. 			l = n / k;
  94. 			//laを√l(小数点以下切捨て)に設定
  95. 			la = (int)sqrt(l);
  96. 			//lが平方数(la^2=l)ならlaを-1する
  97. 			if(la*la == l){
  98. 				la--;
  99. 			}
  100. //printf("i=%d k=%d l=%d la=%d\n",i,k,l,la);
  101. 			do {
  102. 				//laがlの約数ではない場合はスキップする
  103. 				if((l % la) == 0 ){
  104. 					lb = l / la;  //lbを設定
  105. 					//laとlbの最大公約数が1でなければスキップ
  106. 					if (gcm(la,lb) == 1){
  107. 						//(lb-la)*kがmin_dを下回るならa,b,min_dの更新を行いループから抜ける
  108. 						if (((lb - la)*k)<= min_d) {
  109. 							a = k * la ;
  110. 							b = k * lb ;
  111. 							min_d = (lb - la)*k;
  112. 							break ;
  113. 						}
  114. 					}
  115. 				}
  116. 				la-- ; //laを減らす
  117. 			}while(la >= 1); //laの最小値は1
  118.  
  119. 			k = n / i ;
  120. 			//kがmin_dより大きければスキップ
  121. 			if (k <= min_d){
  122. 				l = n / k;
  123. 				//laを√l(小数点以下切捨て)に設定
  124. 				la = (int)sqrt(l);
  125. 				//lが平方数(la^2=l)ならlaを-1する
  126. 				if(la*la == l){
  127. 					la--;
  128. 				}
  129. //printf("i=%d k=%d l=%d la=%d\n",i,k,l,la);
  130. 				do {
  131. 					//laがlの約数ではない場合はスキップする
  132. 					if((l % la) == 0 ){
  133. 						lb = l / la;  //lbを設定
  134. 						//laとlbの最大公約数が1でなければスキップ
  135. 						if (gcm(la,lb) == 1){
  136. 							//(lb-la)*kがmin_dを下回るならa,b,min_dの更新を行いループから抜ける
  137. 							if (((lb - la)*k)<= min_d) {
  138. 								a = k * la ;
  139. 								b = k * lb ;
  140. 								min_d = (lb - la)*k;
  141. 								break ;
  142. 							}
  143. 						}
  144. 					}
  145. 					la-- ; //laを減らす
  146. 				}while(la >= 1); //laの最小値は1
  147. 			}
  148. 		}
  149. 		i ++ ;
  150. //	}while((i * i) < n ); //i<√nまで計算  ←iが大きな値の場合桁あふれが発生
  151. 	}while(i < sqrt(n) ); //i<√nまで計算
  152.  
  153. 	//nが平方数の場合はk=√nの場合があるのでこれを計算
  154. 	if (i*i == n){
  155. 		k = i ;
  156. 		l = n / k ;
  157. 		//laを√l(小数点以下切捨て)に設定
  158. 		la = (int)sqrt(l);
  159. 		//lが平方数(la^2=l)ならlaを-1する
  160. 		if(la*la == l){
  161. 			la--;
  162. 		}
  163. 		do {
  164. 			//laがlの約数ではない場合はスキップする
  165. 			if((l % la) == 0 ){
  166. 				lb = l / la;  //lbを設定
  167. 				//laとlbの最大公約数が1でなければスキップ
  168. 				if (gcm(la,lb) == 1){
  169. 					//(lb-la)*kがmin_dを下回るならa,b,min_dの更新を行いループから抜ける
  170. 					if ((lb - la)<= min_d) {
  171. 						a = k * la ;
  172. 						b = k * lb ;
  173. 						min_d = (lb - la);
  174. 						break ;
  175. 					}
  176. 				}
  177. 			}
  178. 			la-- ; //laを減らす
  179. 		}while(la >= 1); //laの最小値は1
  180.  
  181. 	}
  182.  
  183. 	//最終的にa,bに格納された値を表示して終了する
  184. 	printf("a = %d , b = %d\n", a , b);
  185. 	return ;
  186. }
  187.  
  188. /*
  189. gcm関数の定義
  190. 数値v1と数値v2の最大公約数を求める
  191. */
  192. int gcm (int v1 , int v2){
  193.  
  194. //printf("[gcm]called v1=%d v2=%d",v1,v2);	
  195. 	//v1<=v2かを判定。
  196. 	if (v1 > v2) {
  197. 		return gcm (v2,v1);
  198. 	}
  199. 	int vt;
  200.  
  201. 	//v2%v1が0ならv1が最大公約数となる
  202. 	while ((v2 % v1) != 0){
  203. //printf(" /v1=%d v2=%d",v1,v2);
  204. 		//でなければv1←v2%v1 v2←v1として再計算
  205. 		vt = v1 ;
  206. 		v1 = v2 % v1 ;
  207. 		v2 = vt ;
  208. 	}
  209. //printf(" /return %d\n",v1);
  210. 	return v1 ;
  211. }
  212.  
Success #stdin #stdout 0.02s 4264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
n = 360 → a = 36 , b = 40
n = 1000 → a = 200 , b = 250
n = 3000 → a = 120 , b = 125
n = 5040 → a = 140 , b = 144
n = 5400 → a = 216 , b = 225
n = 9000 → a = 360 , b = 375
n = 1088391168 → a = 497664 , b = 531441
n = 1338557220 → a = 437437 , b = 437580
n = 1000009961 → a = 1 , b = 1000009961
n = 2000019922 → a = 2 , b = 1000009961
n = 357912991 → a = 1 , b = 357912991
n = 2147477946 → a = 6 , b = 357912991
n = 2147483646 → a = 65534 , b = 65538
n = 2147483629 → a = 1 , b = 2147483629
n = 13693680 → a = 11088 , b = 11115
n = 232792560 → a = 248710 , b = 248976
n = 2095502089 → a = 1638391 , b = 1640957
n = 2082117833 → a = 1615297 , b = 1622851
https://ideone.com/S4H5Mo
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!