SHARE
TWEET

Task

a guest Jan 23rd, 2012 208 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <memory.h>
  4. #include <string.h>
  5. #include <math.h>
  6. #include <algorithm>
  7. #include <set>
  8. #include <map>
  9. #include <string>
  10. #include <vector>
  11.  
  12.  
  13. #define INPUT_FILE "input.txt"
  14. #define OUTPUT_FILE "output.txt"
  15. #define clear(x) memset(x,0,sizeof(x))
  16. #define fill(a,b) memset(a,b,sizeof(a))
  17. #define Forn(i,y) for (int i=0; i<(y); i++)
  18. #define Fornr(i,y) for (int i=(y)-1; i>=0; i--)
  19. #define Forp(i,x,y) for (int i=(x); i<=(y); i++)
  20. #define Forpr(i,x,y) for (int i=(x); i>=(y);i--)
  21. #define pb push_back
  22.  
  23. typedef long long ll;
  24. typedef std::pair< int, int> pii;
  25. const int INF = 2147483647;
  26. const int MaxC = 200010;
  27.  
  28. using namespace std;
  29.  
  30. int phi(int x)
  31. {
  32.         if (x==1) return 2;
  33.         int result=x;
  34.         for (int i=2; i*i<=x; i++)
  35.                 if (x%i==0)
  36.                 {
  37.                         while (x%i==0) x/=i;
  38.                         result-=result/i;
  39.                 }
  40.         if (x>1) result-=result/x;
  41.         return result;
  42. }
  43.  
  44. int gcd(int a, int b)
  45. {
  46.         while (b)
  47.         {
  48.                 a%=b;
  49.                 swap(a,b);
  50.         }
  51.         return a;
  52. }
  53.  
  54. int main()
  55. {
  56.         #ifndef ONLINE_JUDGE
  57.         freopen(INPUT_FILE,"r",stdin);
  58.         freopen(OUTPUT_FILE,"w",stdout);
  59.         #endif
  60.  
  61.         ll n;
  62.         scanf("%I64d",&n);
  63.         while (n!=0)
  64.         {
  65.                 ll ans=0,pre;
  66.                 int m=0;
  67.                 for (int i=1; i<=MaxC; i++)
  68.                 {
  69.                         pre=(ll)phi(i);
  70.                         if (n<=ans+pre)
  71.                         {
  72.                                 m=i;
  73.                                 break;
  74.                         }
  75.                         else
  76.                                 ans+=pre;
  77.                 }
  78.                 ll q=0;
  79.                 for (int i=0; i<=m; i++)
  80.                 {            
  81.                         q+=(gcd(i,m)==1);
  82.                         if (ans+q==n)
  83.                         {
  84.                                 printf("%d/%d\n",i,m);
  85.                                 break;
  86.                         }
  87.                 }
  88.                 scanf("%I64d",&n);
  89.         }
  90.  
  91.         #ifdef ONLINE_JUDGE
  92.         fclose(stdin); fclose(stdout);
  93.         #endif
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top