非常好的递推
公式啥的懒得写了,直接放链接哈哈哈https://www.luogu.org/problemnew/solution/P1291
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define dec(i,x,y) for(register int i=x;i>=y;i--)
#define int long long
#define In freopen("7.in","r",stdin)
#define In2 freopen("8.in","r",stdin)
using namespace std;
inline int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;}
int up,down,s;
inline int gcd(int x,int y){
while(y){int tmp=x%y;x=y;y=tmp;}return x;}
inline int lcm(int x,int y){
int gcdd=gcd(x,y);return x*y/gcdd;}
int cal(int x){int s=;
for(int i=;;i++){s=s*;
if(s>x) return i;}}
signed main(){
int n=read();
if(n==){puts("");return ;}
if(n==){puts("");return ;} dec(i,n,){
if(!up) {up=,down=i;continue;}
int lcmm=lcm(i,down);
up=lcmm/down*up+lcmm/i;
down=lcmm;} up=up*n;
int gcdd=gcd(up,down);
up=up/gcdd,down=down/gcdd; s=up/down;up=up%down; if(up&&down){
int k=cal(s),k2=cal(down);
rep(i,,k) printf(" ");
printf("%lld\n",up);
if(s) printf("%lld",s);
rep(i,,k2) printf("-");printf("\n");
rep(i,,k) printf(" ");
printf("%lld\n",down);}
else printf("%lld",s); return ;
}
完结撒花