fork download
copy 
  1. /*
  2. Linkedin: https://w...content-available-to-author-only...n.com/in/sai-suman-chitturi-9727a2196/
  3. Hackerrank: https://w...content-available-to-author-only...k.com/skynetasspyder?hr_r=1
  4. Codechef: https://w...content-available-to-author-only...f.com/users/suman_18733097
  5. Codeforces: http://c...content-available-to-author-only...s.com/profile/saisumanchitturi
  6. Github: https://g...content-available-to-author-only...b.com/ChitturiSaiSuman
  7. Hackerearth: https://w...content-available-to-author-only...h.com/@chitturi7
  8. SPOJ: Sai Suman Chitturi @out_of_bound
  9. */
  10.  
  11. //	  _____   _    _   __    __     ____     __    _
  12. //	 / ____| | |  | | |  \  /  |   /    \   |  \  | |
  13. //	 | |___  | |  | | |   \/   |  /   _  \  | . \ | |
  14. //	 \____ \ | |  | | | |\__/| | |   /_\  | | |\ \| |
  15. //	 ____| | | \__/ | | |    | | |   __   | | | \ ` |
  16. //	 |_____/ \______/ |_|    |_| |__|  |__| |_|  \__|
  17. //
  18.  
  19. #include <stdio.h>			
  20. #include <stdlib.h>
  21. #include <string.h>
  22. #include <math.h>
  23. #include <stdbool.h>
  24. #include <time.h>
  25. #include <limits.h>
  26. #include <ctype.h>
  27. #include <assert.h>
  28.  
  29. #define and 					&&
  30. #define or 						||
  31. #define not 					!
  32. #define is 						==
  33. #define newline 				printf("\n")
  34. #define space					printf(" ")
  35. #define endl					printf("\n")
  36. #define iter(x,a,b) 			for(int x=a;x<=b;x++)
  37. #define FOR(x,N) 				for(int x=0;x<N;x++)
  38. #define For(x,N) 				for(int x=0;x<N;x++)
  39. #define caseprint 				printf("Case #%d: ",test+1)
  40. #define inverse(a,p) 			power(a,p-2,p)
  41. #define scan(a) 				scanf("%d",&a)
  42. #define scanll(a)				scanf("%lld",&a)
  43. #define print(a) 				printf("%lld",((ll)a))
  44. #define println(a)				printf("%lld\n",((ll)a))
  45. #define getName(var)			#var
  46. #define debug(var)				fprintf(stderr,"%s = %lld\n",getName(var),((ll)var));
  47. #define readInt(arr,nax)		FOR(IT,nax) {scan(arr[IT]);}
  48. #define readLL(arr,nax)			FOR(IT,nax) {scanll(arr[IT]);}
  49. #define write(arr,nax)			FOR(IT,nax) {print(arr[IT]);space;}
  50. #define fill(arr,nax,value)		FOR(IT,nax) {arr[IT] = value;}
  51. #define sort123(arr,nax)		qsort(arr,nax,sizeof(int),ascending)
  52. #define sort321(arr,nax)		qsort(arr,nax,sizeof(int),descending)
  53. #define reverse(arr,nax)		FOR(x,nax/2) {arr[x]=arr[nax-x-1];}
  54. #define newInt(nax)				(int*)malloc(sizeof(int)*nax)
  55. #define newLong(nax)			(ll *)malloc(sizeof(ll)*nax)
  56. #define newString(nax)			(char *)malloc(sizeof(char)*nax)
  57. #define copy(from,to,nax)       FOR(IT,nax) {to[IT] = from[IT];}
  58.  
  59. typedef unsigned long long int ull;
  60. typedef long long int ll;
  61. const ll mod = ((ll)(1e9+7)); // 10**9+7
  62. const ll hell = ((ll)(1e9+9)); // 10**9+9
  63. const ll inf = ((ll)(1e18)); // 10**18
  64.  
  65. static inline void swapInt(int *a, int *b) 		{int temp=*a;*a=*b;*b=temp;}
  66. static inline void swapChar(char *a, char *b)	{char c=*a;*a=*b;*b=c;}
  67. static inline void swapLong(ll *a, ll *b)		{ll temp=*a;*a=*b;*b=temp;}
  68. static inline int setBitCount(ll n)				{int ans=0;for(;n>0;ans+=(n&1),n>>=1);return ans;}
  69. static inline ll gcd(ll a, ll b) 				{for(ll rem;b>0;rem=a%b,a=b,b=rem);return a;}
  70. static inline ll lcm(ll a, ll b) 				{return (a*b)/(gcd(a,b));}
  71. static inline ll max(ll a, ll b) 				{return (a>b?a:b);}
  72. static inline ll min(ll a, ll b) 				{return (a<b?a:b);}
  73. static inline ll mul(ll a, ll b, ll p) 			{return ((a%p*b%p)%p);}
  74. static inline ll add(ll a, ll b, ll p) 			{return ((a%p+b%p)%p);}
  75. static inline ll sub(ll a, ll b, ll p) 			{return ((a%p-b%p)+p)%p;}
  76. static inline int sumOfDigits(ll n) 			{return n>0?n%10+sumOfDigits(n/10):0;}
  77. static inline int numberOfDigits(ll n)			{return n>0?1+numberOfDigits(n/10):0;}
  78. static inline void LLFraction(ll *a, ll *b) 	{ll g = gcd(*a,*b); (*a)/=g; (*b)/=g;}
  79. static inline void IntFraction(int *a, int *b)	{int g = gcd(*a,*b); (*a)/=g; (*b)/=g;}
  80.  
  81. int ascending (const void *a, const void *b)	{return *(int*)a>=*(int*)b?1:-1;}
  82. int descending(const void *a, const void *b)	{return *(int*)b>=*(int*)a?1:-1;}
  83.  
  84. ll power(ll x, ll y, ll p)
  85. {
  86. 	ll result=1;
  87. 	for(;y>0;y>>=1,x=mul(x,x,p))
  88. 	{
  89. 		if(y&1)
  90. 			result = mul(result,x,p);
  91. 	}
  92. 	return result;
  93. }
  94.  
  95. bool isPrime(ll n)
  96. {
  97. 	if(n==0 or n==1)
  98. 		return false;
  99. 	else if(n==2 or n==3)
  100. 		return true;
  101. 	else if(n%2==0 or n%3==0)
  102. 		return false;
  103. 	for(int i=5;i<=sqrt(n);i+=6)
  104. 		if(n%i==0 or n%(i+2)==0)
  105. 			return false;
  106. 	return true;
  107. }
  108.  
  109. typedef struct tuple
  110. {
  111. 	int value;
  112. }tuple;
  113.  
  114. int compare(const void *a,const void *b)
  115. {
  116. 	tuple *t1 = (tuple *)a;
  117. 	tuple *t2 = (tuple *)b;
  118. 	int v1 = t1->value;
  119. 	int v2 = t2->value;
  120. 	return v1>v2?1:-1;
  121. }
  122.  
  123. #define size 2000003 // 2 * 10**6+3
  124.  
  125. int spf[size]={0};
  126. ll count[size] = {0};
  127.  
  128. void preCompute()
  129. {
  130. 	for(int i=1;i<size;i+=2)
  131. 		spf[i]=i;
  132. 	for(int i=2;i<size;i+=2)
  133. 		spf[i]=2;
  134. 	for(int i=3;i*i<size;i+=2)
  135. 		if(spf[i] is i)
  136. 			for(int j=i*i;j<size;j+=i)
  137. 				if(spf[j] is j)
  138. 					spf[j]=i;
  139. }
  140.  
  141. void factor(ll x, ll y) {
  142. 	while(x>1) {
  143. 		ll c = 0;
  144. 		int temp = spf[x];
  145. 		while(x > 1 and spf[x] == temp) {
  146. 			c++;
  147. 			x/=temp;
  148. 		}
  149. 		count[temp] = count[temp] + c * y;
  150. 		// debug(temp);
  151. 		// debug(count[temp]);
  152. 	}
  153. }
  154.  
  155. void solve()
  156. {
  157. 	int n;
  158. 	scan(n);
  159. 	FOR(i,n) {
  160. 		ll x, y;
  161. 		scanll(x);scanll(y);
  162. 		factor(x, y);
  163. 	}
  164. 	ll ans = 1;
  165. 	FOR(i, size)
  166. 		if(count[i] & 1)
  167. 			count[i]--;
  168. 	FOR(i, size) {
  169. 		if(count[i] > 0) {
  170. 			debug(count[i]);
  171. 			ll num = sub(power(i, count[i]+2, mod), 1, mod);
  172. 			ll den = sub(power(i, 2, mod), 1, mod);
  173. 			ll value = mul(num, inverse(den, mod), mod);
  174. 			ans = mul(ans, value, mod);
  175. 		}
  176. 	}
  177. 	println(ans);
  178. }
  179.  
  180. int main()
  181. {
  182. 	int t=1;
  183. 	if(!t) scan(t);
  184. 	preCompute();
  185. 	For(test,t)
  186. 	{
  187. 		// caseprint;
  188. 		solve();
  189. 	}
  190. 	return 0;
  191. }
Success #stdin #stdout #stderr 0.02s 9792KB
comments (?)
stdin
copy 
2
2 2
3 1
stdout
copy 
5
stderr
copy 
count[i] = 2
https://ideone.com/q6ibfq
language:
C (gcc 8.3)
created:
3 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!