0
Your rating: None
CodeChef submission 136785 (C) 

CodeChef submission 136785 (C) plaintext list. Status: TLE, problem SNCK04, contest SNACKDWN. By 3 (3), 2009-11-21 23:57:12.
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. int gcd(int a,int b);
  4. int my_gcd(int a, int b)
  5. {
  6. 	int q,r,t;
  7.  
  8. 	/* Normalize so that 0 < a <= b */
  9. 	if((a == 0)||(b == 0)) return -1;
  10. 	if(a < 0) a = -a;
  11. 	if(b < 0) b = -b;
  12. 	if(b < a){
  13. 		t = b;
  14. 		b = a;
  15. 		a = t;
  16. 	}
  17.  
  18. 	/* Now a <= b and both >= 1. */
  19.  
  20. 	q = b/a;
  21. 	r = b - a*q;
  22. 	if(r == 0)
  23. 		return a;
  24.  
  25. 	return my_gcd(a,r);
  26. }
  27.  
  28. int phi(int n)
  29. {
  30. 	if(n<0)n=-n;
  31. 	/* handle a few trivial boundary cases */
  32. 	if(n<=1)return 0;
  33. 	if(n==2)return 1;
  34. 	if(n==3)return 2;
  35. 	return phiphi(n,2);
  36. }
  37.  
  38. /* This only gets called with y >= 3 and y > x >= 2 */
  39.  
  40. int phiphi(int y, int x)
  41. {
  42. 	int z;
  43.  
  44. 	if(x+1 == y)return x; /* phi(prime p) = p-1 */
  45. 	if((y%x)==0){
  46. 		if(my_gcd(x,z=y/x)==1)
  47. 			return phi(x)*phi(z); /* multiplicative property */
  48. 		else
  49. 			return x*phi(z); /* This is a tricky case. It may
  50. 					    happen when x is a prime such
  51. 					    that a power of x divides y. In
  52. 					    case y = p^n, phi(y) = p^(n-1)(p-1)
  53. 					  */
  54. 	}
  55. 	else return phiphi(y,x+1);
  56. }
  57. int main()
  58. {
  59. 	int i,n,ans,k;
  60. 	int tc;
  61. 	int j,rem,m;
  62. 	scanf("%d",&tc);
  63. 	while(tc--)
  64. 	{
  65. 		scanf("%d",&n);
  66. 		for(i=2,ans=n-1;i<=n;i++)
  67. 		{
  68. 			k=phi(i);
  69. //			printf("phi returns %d\n",k);
  70. 			if(n>i)
  71. 				m=(n/i)-1;
  72. 			else
  73. 				m=0;
  74.  
  75. 			ans+=m*k;
  76. 			rem=n%i;
  77. 			for(j=i*(m+1),rem+=j;j<=rem;j++)
  78. 			{
  79. 				if(gcd(n,j)==1) ans++;
  80. 			}
  81. //			printf("ans is %d\n",ans);
  82. 		}
  83. 		printf("%d\n",ans);
  84. 	}
  85. 	return 0;
  86. }
  87. int gcd(int a,int b)
  88. {
  89. 	if(b==0) return a;
  90. 	return gcd(b,a%b);
  91. }
  92.

Comments