fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define MAX 501
  4. #define EPS 1e-9
  5. #define MOD 1000000007
  6. #define INF 10000000
  7. #define pn() printf("\n")
  8. #define vint vector <int>
  9. #define vpint vector <pair<int,int> >
  10. #define pb push_back
  11. #define mp make_pair
  12. #define ft first
  13. #define sd second
  14. #define gc() getchar_unlocked()
  15. #define ms(x,v) memset(x,v,sizeof x)
  16. #define pr_arr(i,x,size) for(i=0;i<size;i++) cout<<x[i]<<" "
  17. #define ff(i,a,b) for(i=a;i<=b;i++)
  18. #define fb(i,a,b) for(i=a;i>=b;i--)
  19. #define gprint(i) cout<<"Case #"<<i<<": "
  20. using namespace std;
  21.  
  22. int dp[MAX][MAX];
  23.  
  24. void init_dp()
  25. {
  26. 	int i;
  27. 	for(i=0;i<MAX;i++)
  28. 	{
  29. 		dp[i][0]=INF;
  30. 		dp[0][i]=INF;
  31.  
  32. 	}
  33. }
  34.  
  35. void create_dp()
  36. {
  37. 	init_dp();
  38. 	int i,j;
  39. 	for(i=1;i<MAX;i++)
  40. 	{
  41. 		for(j=1;j<MAX;j++)
  42. 		{
  43. 			if(i==1 && j==1)
  44. 				continue;
  45. 			int gcd=__gcd(i,j);
  46. 			int mini=INT_MAX;
  47. 			if(gcd!=1)
  48. 			{
  49. 				mini=min(mini,dp[i/gcd][j/gcd]+1);
  50. 			}
  51. 			mini=min(mini,min(dp[i-1][j],dp[i][j-1])+1);
  52. 			dp[i][j]=mini;
  53. 		}
  54. 	}
  55.  
  56. }
  57.  
  58. int main()
  59. {
  60.     ios::sync_with_stdio(false);
  61.     create_dp();
  62.     int t;
  63.     cin>>t;
  64.     while(t--)
  65.     {
  66.     	int n,m;
  67.     	cin>>n>>m;
  68.     	cout<<dp[n][m]<<endl;
  69.     }
  70.     return 0;
  71. }
Runtime error #stdin #stdout 0.01s 4444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8diYl1
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

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!