1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include<bits/stdc++.h> #define ll long long #define fsb(a,b,c) for(ll a=b;a<=c;a++) #define fbs(a,b,c) for(ll a=b;a>=c;a--) using namespace std; ll n,a=0,b=1; template<typename qw>inline void rll(qw &x){ x=0;qw f=1;char c=getchar(); while(!isdigit(c))f=c=='-'?-1:f,c=getchar(); while(isdigit(c))x=x*10+c-'0',c=getchar(); x*=f; } inline ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); } inline void add(ll aa,ll bb){ ll k=gcd(b,bb),ansa,ansb; ansb=b/k*bb;ansa=b/k*aa+bb/k*a; k=gcd(ansa,ansb); a=ansa/k;b=ansb/k; } inline ll len(ll x){ ll ans=0; while(x>0){ ans++;x/=10; } return ans; } int main(){ rll(n); fsb(i,1,n){ ll aa=n,bb=i,k=gcd(aa,bb); aa/=k;bb/=k; add(aa,bb); } if(a%b==0){ printf("%lld\n",a/b); }else{ ll x=a/b;a-=x*b;ll lx=len(x),lb=len(b); fsb(i,1,lx)printf(" ");printf("%lld\n",a); printf("%lld",x);fsb(i,1,lb)printf("-");puts(""); fsb(i,1,lx)printf(" ");printf("%lld\n",b); } return 0; }
|