20200616题解

# 等式/equal - 题目： 给出$n$,求 $$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$$ 中$x$,$y$的解集个数($x\leq y$) ------ - 分析 因为($x\leq y$)，所以我们可以很明显的想到设$x=\frac{1}{n+x}$ 所以我们可以据此表示$y=\frac{x}{(n)\times(x+n)}$ 所以我们现在就是要知道$y$可不可以表示成$\frac{1}{m}$ 那么$\frac{1}{y}=m=\frac{(n)\times(x+n)}{x}=\frac{n^2}{x}+n$ 所以我们只需要让$\frac{n^2}{x}$为整数 这就很明显的得出： 我们先让$n$分解质因数，然后每一个质因子的数用质因数个数的公式： $$num_n=\prod\limits_{i\mid n,i\in prime}num[i]$$ 然后我们可以看出，每一个小于$n$的可以被$n^2$整除的数，都与一个大于$n$的可以被$n^2$整除的数**一一对应**，所以说最后的答案就显而易见了。 （你想知道为什么一一对应吗，私聊我吧） - **Codes** ```cpp #include<cstdio> #include<iostream> #include<cstring> #define ri register int #define Starseven main #define ll long long using namespace std; ll read(); void write(ll);//要记得自己加换行和空格 ll n,prime[10000+20],num; ll ans; bool vis[40000+20]; void Init(){ freopen("equal.in","r",stdin); freopen("equal.out","w",stdout); } void Cut(){ ans=1; for(ri i=1;i<=num;i++){ ll x=0; while(n%prime[i]==0) x+=2,n/=prime[i]; ans=(x+1)*ans; if(n==1) break; } if(n!=1) ans=ans*3; ans+=1; ans/=2; write(ans); puts(""); } int Starseven(void){ Init(); ll t=read(); for(ri i=2;i<=40000;i++){ if(!vis[i]) prime[++num]=i; for(ri j=1;j<=num&&prime[j]*i<=40000;j++){ vis[i*prime[j]]=true; if(!i%prime[j]) break; } } while(t--){ n=read(); Cut(); } return 0; } ll read(){ char ch=getchar(); ll re=0,op=1; while(ch<'0'||ch>'9'){ if(ch=='-') op=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ re=(re<<3)+(re<<1)+ch-'0'; ch=getchar(); } return re*op; } void write(ll x){ if(x<0){ putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); return ; } ``` ---------- # 湾海公园/park - 题目 给你一个$n$个点，$n$条边的图，保证拆一条边可以变成树，然后每个边都有权值，叫你拆一条边，保证以下两点 - 保证是棵树 - 保证此时树的直径最短 然后输出此时的树的直径 -------------- - 分析 我们首先可以知道，此时的图由于拆一个边就可以变成树，所以这个图里只有一个环 那我们先用无向图的拓扑排序来求出环。这期间可以处理出环上每个点 -