fork download
copy 
  1. #include <iostream>
  2. #include <cstdint>
  3. #include <tuple>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <numeric>
  7.  
  8. typedef std::tuple<std::size_t, std::size_t> VType;
  9. typedef std::vector<VType> DType;
  10.  
  11. //パクってきた：http://k...content-available-to-author-only...e.jp/prog/c/tip0000a.shtml
  12. //C++17で入るのでそっちを使ってくれ。
  13. //*********************************************************
  14. // 最大公約数（Greatest Common Divisor）を返す。
  15. // 引数に０がある場合は０を返す。
  16. //*********************************************************
  17. template<class T>
  18. T gcd(T m, T n)
  19. {
  20. 	// 引数に０がある場合は０を返す
  21. 	if ((0 == m) || (0 == n))
  22. 		return 0;
  23.  
  24. 	// ユークリッドの方法
  25. 	while (m != n)
  26. 	{
  27. 		if (m > n) m = m - n;
  28. 		else         n = n - m;
  29. 	}
  30. 	return m;
  31. }//gcd
  32.  
  33. DType EnumFareySequence(const std::uint64_t& N) {
  34. 	DType R;
  35. 	R.push_back({0,1});
  36. 	for (std::size_t i = 1; i <= N; i++) {
  37. 		for (std::size_t j = 1; j < i; j++) {
  38. 			if(gcd(i,j)==1)R.push_back({ j,i });
  39. 		}
  40. 	}
  41. 	R.push_back({ 1,1 });
  42. 	std::sort(R.begin(), R.end(), [](VType& A, VType B) {
  43. 		std::uint64_t A1, A2;
  44. 		std::uint64_t B1, B2;
  45.  
  46. 		std::tie(A1, A2) = A;
  47. 		std::tie(B1, B2) = B;
  48.  
  49. 		return (A1 / static_cast<double>(A2)) < (B1 / static_cast<double>(B2));
  50. 	});
  51. 	return R;
  52. }
  53.  
  54. VType MakeHoge(std::size_t N,std::size_t P) {
  55. 	DType D = EnumFareySequence(N);
  56.  
  57. 	return (P-1 >= D.size()) ? (VType{ 1, 1 }) : D[P-1];//何で無名初期化子がつかえないのかにゃ？
  58. }
  59.  
  60. bool Show(const std::size_t& N, const std::size_t& P, const VType& V) {
  61.  
  62. 	std::cout << N << 'D' << P << "th => " << std::get<0>(V) << '/' << std::get<1>(V) << std::endl;
  63. 	return true;
  64.  
  65. }
  66.  
  67. int main() {
  68. 	std::size_t N = 5;
  69. 	std::size_t P = 4;
  70. 	VType V;
  71.  
  72. 	V = MakeHoge(N,P);
  73. 	Show(N, P, V);
  74.  
  75. 	N = 24;
  76. 	P = 17;
  77.  
  78. 	V = MakeHoge(N,P);
  79. 	Show(N, P, V);
  80. 	return 0;
  81.  
  82. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5D4th => 1/3
24D17th => 2/21
https://ideone.com/m7BnJN
language:
C++14 (gcc 8.3)
created:
6 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!