fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*long long pot(long long x,long long m)
  5. {
  6. 	long long a = 1;
  7. 	for(long long i = 0;i < m-2;++i)
  8. 	{
  9. 		a *= x;
  10. 		a %= m;
  11. 	}
  12. 	return a;
  13. }*/
  14.  
  15. long long pot(long long x,long long m,long long mod)
  16. {
  17. 	if(m==0)
  18. 		return 1;
  19. 	if(m%2 == 1)
  20. 		return (x * pot(x, m - 1,mod))%mod;
  21. 	long long w = pot(x, m/2,mod); 
  22. 	return (w * w)%mod;
  23. }
  24.  
  25. long long nwd(long long a,long long b)
  26. {
  27. 	return a*b/__gcd(a,b);
  28. }
  29.  
  30. vector<long long> dziel(long long n)
  31. {
  32. 	vector<long long> wyn;
  33. 	for(long long i = 1;i*i <= n;++i)
  34. 	{
  35. 		if(n%i == 0)
  36. 		{
  37. 			wyn.push_back(i);
  38. 			wyn.push_back(n/i);
  39. 			//n /= i;
  40. 		}
  41. 	}
  42. 	return wyn;
  43. }
  44.  
  45. pair<long long,long long> best(long long n,long long m)
  46. {
  47. 	long long wyn = 1e9;
  48. 	pair<long long,long long> k;
  49. 	for(int i = 1;i <= n;++i)
  50. 	{
  51. 		if(__gcd((nwd(n,i)/i)%m,m) == 1)
  52. 		{
  53. 			//wyn = min(wyn,i+pot(n/i,m));
  54. 			if(wyn > i+1)
  55. 			{
  56. 				wyn =  i+1;
  57. 				k = {i,1};
  58. 			}
  59. 		}
  60. 	}
  61. 	return k;
  62. }
  63.  
  64. int main()
  65. {
  66. 	ios_base::sync_with_stdio(0);
  67. 	long long n,m;
  68. 	cin >> n >> m;
  69. 	//cout << best(n,m).first << ' ' << best(n,m).second;
  70. 	if(__gcd(n,m) == 1 || __gcd(n,m) == 2)
  71. 	{
  72. 		cout << 2 << endl << "DP";
  73. 		return 0;
  74. 	}
  75. 	pair<long long,long long> a = best(n,m);
  76. 	if(n < a.first+a.second) a = {n-1,1};
  77. 	pair<long long,long long> b = best(m,n);
  78. 	if(m < b.first+b.second) b = {m-1,1};
  79. 	if(a.first+a.second  < b.first+b.second)
  80. 	{
  81. 		cout << a.first+a.second << endl;
  82. 		for(long long i = 0;i < a.first;++i)
  83. 		{
  84. 			cout << 'D';
  85. 		}
  86. 		for(long long i = 0;i < a.second;++i)
  87. 		{
  88. 			cout << 'P';
  89. 		}
  90. 	}
  91. 	else
  92. 	{
  93. 		cout << b.first+b.second << endl;
  94. 		for(long long i = 0;i < b.first;++i)
  95. 		{
  96. 			cout << 'P';
  97. 		}
  98. 		for(long long i = 0;i < b.second;++i)
  99. 		{
  100. 			cout << 'D';
  101. 		}
  102. 	}
  103. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
2 2
stdout
copy 
2
DP
https://ideone.com/JhFEdn
language:
C++ (gcc 8.3)
created:
13 days 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!