题解 Luogu P3708 koishi的数学题

作者: MayFlyyh 分类: 模拟 发布时间: 2018-03-01 18:12 ė 6 没有评论

P3708 koishi的数学题

题目描述
Koishi想了一道简单数学题

输入一个整数n



你需要输出f(1),f(2)…f(n) 。

按照套路,Koishi假装自己并不会做这道题,就来求你帮忙辣。

输入一个正整数n。

输出:
一行用空格分隔的n个整数f(1),f(2)…f(n)

输入样例:10

输出样例:
9 16 22 25 29 27 29 24 21 13

对于20%的数据,

对于60%的数据,

对于100%的数据,

对于20的数据,暴力直接算

对于100的数据…先打个表看看?

表1

横行为x 纵行为i

对于每个x,横行之和就是答案,但是暴力算只能得20

再看每个纵行,发现了神奇的规律,每个纵行好像都是一个循环数列

对于每个i,x mod i总为0,1,2,3,…,i-1,0,1,2,3,…,i-1,….

但这个循环纵列终究不好看,顺着纵行的思路,我们计算x-(x mod i)

表2

更不得了了!

然后我们记录 x – x mod i,得到0,0,0,0,…0,i,i,i,…,i,2i,…,2i,…

我们发现,每行的答案,便是i*n减去每行的数字

那么我们可以维护差分数组,我们发现,每横行的第i个数

总是在 x多了i 的情况下,增加i

如第3列,x本来为0,增加3后为第3行,数字为3

再增加3后为第6行,数字为6

其间的不变,于是我们发现,对于第x行,对于,每i行需要多减一个i

    for(int i=1;i<=n;++i)//从左往右扫
        for(int j=i;j<=n;j+=i){ /从上往下扫,增加了i就加上i
            num[j]+=i;
        }

完整代码:

#include<bits/stdc++.h>
#define N 1000100
long long num[N];
int n;  long long ans; 
int main (){
    scanf("%d",&n);  //x-(x mod i)
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;j+=i){
            num[j]+=i;
        }
    ans=n-1;
    printf("%d ",ans);
    for(int i=2;i<=n;++i){
        ans+=n-num[i];
        printf("%lld ",ans);
    }
}

小小的一道题还是需要思考的,能总结出规律也不易

机智的你,可以在考场上思考出正解吗?

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/145

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部