FCOI #11 官方题解

sfqxx

https://fishc.com.cn/thread-237169-1-1.html 验题人题解，把我吊打了%%%

这里是 官方题解！

A-互关

一道简单模拟题，很快就能 AC ，就不讲了。

B-高斯记号


这里提供一个不一样的思路，出题人是用字符串做的调了好几次。

显然，第一种情况为将输入的数转换为整数（向下取整），第2种情况直接模拟

代码：

a,b=map(str,input().split())
if a=="1":
    print(int(float(b)))
else:
    c = list(b.split("."))
    print("0."+c[1])

C 只因出现一次的数字

思路与验题人题解差不多，且本人代码可读性较差，不放了

D - 枪战

签到题放完了，我们从现在开始没有这么简单了。

考虑直接模拟，时间复杂度为 O(n²)，显然无法通过此题

考虑单调栈，与其不如求解一个人能干掉几个人，不如计算一个人能被几个人干掉，于是我们用栈模拟即可。

n=int(input())
b=0
st=[]
for i in range(n):
    a=int(input())
    while st and st[-1]<=a:
        st.pop()
    b+=len(st)
    st.append(a)
print(b)
    

注意单调栈不要写错，我看 tommyu 好像就是拿了90pts就是因为这个原因（？

E 可恶的 zhangjinxuan

求证过程可以看验题人题解，出题人咕咕了

这道题可以用 Python 做，因为无需用高精度。

F -  高斯记号

这道题可以套用 Python 中的eval

我们可以先将输入数据的高斯记号整理为正常表达式，然后注意精度。

（压轴题）G - 公因数

给定一个整数 $n$，你需要求出 $\sum\limits_{i=1}^n \gcd(i, n)$，其中 $\gcd(i, n)$ 表示 $i$ 和 $n$ 的最大公因数。  

本题难点在于思路。

暴力可得 65 or 70 pts

正解：

我们先来看一张图：

                               
登录/注册后可看大图

思路开始：注意到 gcd(i,n) 一定是 n 的约数，n 的约数却很少（最多为 d(n) 个）。考虑枚举 n 的约数（设为 d）, 再求出满足 gcd (i,n) = d 的 i 有多少个即可。考虑 i = i'd,那么必然有 i ⊥(n/d) 且 1 ≤ i ≤ (n/d)
(论坛打不出分数)。这样的i'(i)有 φ (n/d) 个。 对于 n 的每一个约数，也直接求出他的欧拉函数即可。

注意到 n 的约数 d 的约数 也一定是 n 的约数，所以在枚举 d 的约数 求解 φ(d) 时只要枚举之前求出的比 d 小的 n 的约数即可。时间复杂度为 O(√￣n + d²(n))。

#include<cstdio>
long long n;
long long f(){
    long long ans=n; long long i;
    for(i=2;i*i<=n;++i) if(n%i==0){
        int b=0;
        while(n%i==0) ++b,n/=i;
        ans/=i;
        ans*=b*i-b+i;
    } if(n>1) ans/=n, ans*=n+n-1; 
    return ans;
}
int main(){
    scanf("%lld",&n);
    printf("%lld",f());
    return 0;
}

zhangjinxuan

官方题解没人啊

sfqxx

zhangjinxuan 发表于 2023-12-2 16:25
官方题解没人啊

是啊