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. */
  10. void solve(int);
  11. int gcm(int , int);
  12.  
  13.  
  14. int main(){
  15. //printf("[main]called\n\n");
  16. 	solve(       360); 
  17. 	solve(      1000);
  18. 	solve(      3000);
  19. 	solve(      5040);
  20. 	solve(      5400);
  21. 	solve(      9000);
  22. 	solve(1088391168);
  23. 	solve(1338557220);
  24. 	solve(1000009961);
  25. 	solve(2000019922);
  26. 	solve( 357912991);
  27. 	solve(2147477946);
  28. 	solve(2147483646);
  29. 	solve(2147483629);
  30. 	solve(  13693680);
  31. 	solve( 232792560);
  32. 	solve(2095502089);
  33. 	solve(2082117833);
  34. }
  35.  
  36. void solve(int n){
  37. //printf("[solve]called\n");
  38. 	printf("n = %d → ",n);
  39. 	// nが1の場合はn=a=b=1となり解なし
  40. 	if (n <= 1){
  41. 		printf("no answer\n");
  42. 		return ;
  43. 	}
  44.  
  45. 	/*
  46. 	aとbを求めるにあたり、以下の値を仮定する
  47. 	　k :laとlbの最大公約数　nの約数のいずれか
  48. 	　　la*lb=nとなる
  49. 	　la:a/kとなる数　nの約数のいずれか
  50. 	　lb:b/kとなる数　nの約数のいずれか
  51. 	　min_d:k*(lb-la)の最小値
  52. 	*/
  53. 	int a = 0 , b = 0 ;
  54. 	int k , la , lb;
  55. 	int min_d = n; //仮にnを設定。実際にはk=1,la=1,lb=nの時に最大となり必ず(n-1)以下の値で更新される
  56.  
  57. 	/*
  58. 	まずnをla*lb=nとなるような２つの数la,lbに分解する
  59. 	この時(lb-la)が出来るだけ小さくなるように√n未満からlaを探し出していく。
  60. 	*/
  61. 	la = (int)sqrt(n);
  62. 	//nが平方数(la^2=n)ならlaを-1する
  63. 	if ((la*la) == n) {
  64. 		la --;
  65. 	}
  66. 	do {
  67. 		//laがnの約数ではない場合はスキップする
  68. 		if((n % la) == 0){
  69. 			lb = n / la ; //lbを設定
  70.  
  71. 			//laとlbの最大公約数を調べる。
  72. 			k = gcm(la,lb);
  73.  
  74. 			//(lb-la)*kがmin_dを下回るならa,b,min_dの更新を行う
  75. 			if (((lb - la) * k) <= min_d) {
  76. 				//la,lbにそれぞれkを掛けた値をa,bとする
  77. 				a = la * k ;
  78. 				b = lb * k ;
  79. 				min_d = (lb - la) * k ;
  80. 			}
  81. 		}
  82. 		la-- ; //laを減らす
  83. 	}while(la >= 1); //laの最小値は1
  84.  
  85. 	//最終的にa,bに格納された値を表示して終了する
  86. 	printf("a = %d , b = %d\n", a , b);
  87. 	return ;
  88. }
  89.  
  90. /*
  91. gcm関数の定義
  92. 数値v1と数値v2の最大公約数を求める
  93. */
  94. int gcm (int v1 , int v2){
  95.  
  96. //printf("[gcm]called v1=%d v2=%d",v1,v2);	
  97. 	//v1<=v2かを判定。
  98. 	if (v1 > v2) {
  99. 		return gcm (v2,v1);
  100. 	}
  101. 	int vt;
  102.  
  103. 	//v2%v1が0ならv1が最大公約数となる
  104. 	while ((v2 % v1) != 0){
  105. //printf(" /v1=%d v2=%d",v1,v2);
  106. 		//でなければv1←v2%v1 v2←v1として再計算
  107. 		vt = v1 ;
  108. 		v1 = v2 % v1 ;
  109. 		v2 = vt ;
  110. 	}
  111. //printf(" /return %d\n",v1);
  112. 	return v1 ;
  113. }
  114.  
Success #stdin #stdout 0s 4284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
n = 360 → a = 36 , b = 40
n = 1000 → a = 125 , b = 200
n = 3000 → a = 500 , b = 600
n = 5040 → a = 140 , b = 144
n = 5400 → a = 216 , b = 225
n = 9000 → a = 72 , b = 125
n = 1088391168 → a = 165888 , b = 531441
n = 1338557220 → a = 109395 , b = 110124
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 = 42966 , b = 49981
n = 2147483629 → a = 1 , b = 2147483629
n = 13693680 → a = 11088 , b = 11115
n = 232792560 → a = 14960 , b = 15561
n = 2095502089 → a = 1283 , b = 1633283
n = 2082117833 → a = 1289 , b = 1615297
https://ideone.com/HdfYPe
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!