fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. bool mark[40009];
  5. vector<long long> prime;
  6. void sieve()
  7. {
  8. 	for (long long i=3; i<=200; i+=2)
  9. 	{
  10. 		if (!mark[i])
  11. 			for (long long j=i*i; j<=40000; j+=2*i)
  12. 				mark[j]=true;
  13. 	}
  14. 	prime.pb(2);
  15. 	for (long long i=3; i<=40000; i+=2)
  16. 		if (mark[i]==false)
  17. 			prime.pb(i);
  18. }
  19. void check(long long p,long long r,long long q,long long s)
  20. {
  21. 	map<long long,long long> m1,m2;
  22. 	map<long long,long long> ::iterator it;
  23. 	long long num1=p,num2=q,flag=0;
  24. 	for (long long i=0; i<prime.size(); i++)
  25. 	{
  26. 		while (num1%prime[i]==0)
  27. 		{
  28. 			num1/=prime[i];
  29. 			m1[prime[i]]++;
  30. 		}
  31. 	}
  32. 	if (num1>1)
  33. 		m1[num1]++;
  34. 	for (long long i=0; i<prime.size(); i++)
  35. 	{
  36. 		while (num2%prime[i]==0)
  37. 		{
  38. 			num2/=prime[i];
  39. 			m2[prime[i]]++;
  40. 		}
  41. 	}
  42. 	if (num2>1)
  43. 		m2[num2]++;
  44.  
  45. 	for (it=m1.begin(); it!=m1.end(); it++)
  46. 		it->second*=r;
  47.  
  48. 	for (it=m2.begin(); it!=m2.end(); it++)
  49. 		it->second*=s;
  50.  
  51. 	for (it=m2.begin(); it!=m2.end(); it++)
  52. 	{
  53. 		if (m1.find(it->first)==m1.end())
  54. 		{
  55. 			flag=1;
  56. 			break;
  57. 		}
  58. 		if (m1[it->first]<it->second)
  59. 			flag=1;
  60. 	}
  61. 	if (!flag)
  62. 		cout<<"divisible\n";
  63. 	else
  64. 		cout<<"not divisible\n";
  65. }
  66. int main()
  67. {
  68. 	sieve();
  69. 	long long p,q,r,s,t;
  70. 	cin>>t;
  71. 	while (t--){
  72. 		cin>>p>>r>>q>>s;
  73. 		check(p,r,q,s);
  74. 	}
  75. 	return 0;
  76. }
Success #stdin #stdout 0s 3316KB
comments (?)
stdin
copy 
2
18 2 12 1
7 1 2 10
stdout
copy 
divisible
not divisible
https://ideone.com/jAmAAb
language:
C++ (gcc 8.3)
created:
9 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!