Codeforces Round 310 (Div. 2)

考了三道比较简单的数学题（题目来源网络）

题面

傻牛的约数研究(divisor)

Description

傻牛最近在研究约数，它觉得这玩意很牛逼。
首先，对于一个数字 X 来说，设 F(X) 表示 X 的约数个数，可以先将 X 表达成为若干个质数的幂次之积，即 X=p1k1∗p2k2∗...psksX = p_1k_1*p_2k_2 * ... p_sk_s，然后F(X)=(k1+1)∗(k2+1)∗...∗(ks+1)F(X)=(k_1+1) * (k_2+1) * ... * (k_s+1).傻牛觉得这个碉堡了。有一天它想，我们是不是可以求出 F(1)+F(2)+F(3)+……+F(N)F(1)+F(2)+F(3)+……+F(N) 的值呢？结果，它晕掉了。

Solution

答案即为1 ~ n所有数的约束的个数和。
当然可以利用分解质因数直接求，但是有更机智的方法。
枚举i = 1 … n, n / i即为以i为因数的数的个数，所以答案即为 Σi=1nni\Sigma_{i=1}^n \frac{n}{i};
代码8行.

Code

1
2
3
4
5
6
7
8
#include<cstdio>
int main(){
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) ans+=n/i;
    printf("%d",ans);
    return 0;
}

傻牛的递推数列(sequence)

Description

傻牛最近钻研各类数学递推数列。尤其是斐波那契数列。
傻牛眼中的斐波那契数列是这样的， F1=1， F2=1，然后 Fi+2=Fi+1 + Fi，逐项递推。
今天，傻牛发现，某些斐波那契项之间是成倍数关系的。例如第 4 项 F4=3 和第 8 项 F8=21。
傻牛想知道，对于某一项 Fx，求所有满足 Fi 是 Fx 是 Fi 倍数的 i 的和是多少？

Solution

发现了斐波那契数列一个很神奇的性质，对于任意x>2,任意x>i的F[i]是F[x]的约数当且仅当i是x的约数。（可自行证明）
于是题目转化为，求x的约数和…注意特判
代码依然很简单

Code

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>

const int maxn=1000000; int ans[maxn+1];

int main(){
    int n;
    for(int i=3;i<=maxn;i++)
     for(int j=i;j<=maxn;j+=i) ans[j]+=i;
    while(~scanf("%d",&n)) printf("%d\n",ans[n]+3);
    return 0;

}

傻牛的数字游戏(Game)

Description

傻牛最近在玩一个数字游戏。
首先，规定一个神奇的数字 P，它就是 1000000007。
这个游戏是这样的，首先给你一个无比巨大的数字（1000000006!）^1000000006，当然，这个
数字对 P 的模值为 1。然后，游戏可能给你以下两种操作之一，第一种操作就是将这个数乘以一个
数字 X，第二种操作就是将这个数字除以一个数字 X。要求输出每种操作过后这个数字对 P 的模值。
现在，傻牛的菊花痒了，要去上厕所了，你不得不帮他玩一盘。

Solution

乘法很容易做，就是当前模数*x再模p,除法就是乘上x的逆元再模p.

这里不再赘述代码

总结

学到的姿势:
斐波那契数列神奇的性质
n约数个数的求法
n的约数和
1 ~ n的约数和

Comment