fork(2) download
copy 
  1. /**********************************************************************************/
  2. /*  Problem: d230 "IOI研習營模考2-1三元樹" from IOI                       */
  3. /*  Language: CPP (644 Bytes)                                                     */
  4. /*  Result: AC(0.4s, 288KB) judge by this@ZeroJudge                               */
  5. /*  Author: lfs92002 at 2014-03-14 09:16:05                                       */
  6. /**********************************************************************************/
  7.  
  8.  
  9. #include<cstdio>
  10. #include<algorithm>
  11. using namespace std;
  12. #define MOD 10000000
  13. int base[15001];
  14. inline int gcd(int a,int b)
  15. {
  16. 	while((a%=b)&&(b%=a));
  17. 	return a+b;
  18. }
  19. int main()
  20. {
  21. 	int n;
  22. 	int p,j;
  23. 	while(~scanf("%d",&n))
  24. 	{
  25. 		for(int i=2*n+1;i<=3*n;++i)
  26. 			base[i]=i;
  27. 		for(int i=1;i<=n;++i)
  28. 		{
  29. 			p=i,j=2*n+1;
  30. 			while(p!=1)
  31. 			{
  32. 				int d=gcd(p,base[j]);
  33. 				p/=d;
  34. 				base[j++]/=d;
  35. 			}
  36. 		}
  37. 		p=2*n+1;
  38. 		j=2*n+1;
  39. 		while(p!=1)
  40. 		{
  41. 			int d=gcd(p,base[j]);
  42. 			p/=d;
  43. 			base[j++]/=d;
  44. 		}
  45. 		long long ans=1;
  46. 		for(int i=2*n+1;i<=3*n;++i)
  47. 			ans=ans*base[i]%MOD;
  48. 		printf("%lld\n",ans);
  49. 	}
  50. 	return 0;
  51. }
  52.  
Success #stdin #stdout 0s 3400KB
comments (?)
stdin
copy 
2
3
stdout
copy 
3
12
https://ideone.com/L1pMBW
language:
C++14 (gcc 8.3)
created:
10 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!