以行走般的速度β

Problem Description
In the world line 1.048596
今天的理科实验室依旧回响着气泡的大合唱
梓川咲太一边看应考的题目一边听着声音的变化,同时思索该如何回答考察数学思维的题目…
就算解决了牧之原翔子和樱岛麻衣的问题,也终究要面对现实的考验
“梓川你不是要和樱岛麻衣前辈考同一个大学吗?
双叶理央坐在咲太的面前,今天也依然披着白大褂,正在准备不知名的实验。
“是啊。之前不是说过吗?所以我现在忙于备考。
“我就友善的提醒你一句…
“什么?
“你看的是我的算法竞赛书…”双叶理央用略带担忧的声音这么说着
梓川咲太突然回过神来,他翻了翻书本后面的内容,的确是和程序有关。但是前面的例题部分做的却和普通的参考书别无二致
双叶拿回了她的算法书,找着梓川刚刚在看的部分
“给出一个大于等于2的正整数n,对于一对数a和b(2<=|a|,|b|<=n,a!=b),如果存在一个整数x(|x|>=1)使得ax=b(或bx=a),就可以将a转换成b(或将b转换为a),转换后,你可以获得|x|的积分。
一边说着,双叶就开始在黑板上写一些算式
“不过,限制条件是,转换完毕后,就不能再使用由a转换成b或b转换成a的转换方式了。
”一开始拥有的积分是0,现在给一个大于等于2的正数n,可以在2~n都取一次起点进行转换(更换起点时,转换方式不初始化)。请问最多可以获得多少分?
“双叶老师,我实在是听不懂。
梓川咲太很爽快的袒露了事
比如说n等于4的时候答案是11,因为:
取起点为2时,你的最多得分是9。其中的一种得分方式是 2→(-2)→4→2→(-4)→(-2)
取起点为3时,你只能得1分,3→(-3)
取起点为4时,你别的转换方式都使用过,因此只能得1分,4→(-4)
所以最终答案是9+1+1=11,明白了吗
黑板上已经密密麻麻写了一堆公式,在右下角又写了一个Accepted。看来双叶理央已经在脑内解决了这个问题
不过对于咲太来说这依旧是一个难题。虽然不是应考的范围,但既然看了这么久,也就顺便解答出来吧。

Input
多组输入输出。
对于每一组数据,输入一个整数n(2<=n<=100000)
保证n的个数小于200,n的总和不超过5000000。

Output
对于每一组样例
输出梓川咲太最大能够得到的分数。

Sample Input
2
4
6

Sample Output
1
11
33

题解:一道找规律的题。

  • 当n等于6时,从2开始有2 -> -2,得到的分数是1,如果我们称这为一条分支的话,
  • 由-2继续又有-2 -> 4 -> 2 -> -4 -> -2,得到的分数是4/2*4=8,这时有两条分支。
  • 由-2继续又有-2 -> 6 -> 2 -> -6 -> -2, 得到的分数是6/2*4=12,这时有三条分支。
  • 当n等于8呢,在上面的基础上
  • 由-2继续又有-2 -> 8 -> 2 -> -8 -> -2得到的分数是8/2*4=16,这时有了四条分支。
  • 那么对于任意数n,以2为起点开始有n/2条分支,所得分数为1+24+…+n/24。
  • 那么对于任意数n,以m为启点开始有n/m条分支,所得分数为1+24+…+n/m4。

PS:感谢wcy大佬的思路

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ling long
#define INF 0×3f3f3f3f  //0×7ffffff
#define EPS 1e-6
#define maxn 1000000+10
#define PI acos(-1.0)
using namespace std;
ll a[maxn]={0,1,};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll ans;
    for(int i=2;i<maxn;i++)
        a[i]=a[i-1]+4*i;
    while(cin>>n)
    {
        ans=0;
        for(int i=2;i<=n;i++)
            ans+=a[n/i];
        cout<<ans<<endl;
    }
    return 0;
}

 

发表评论,支持MarkDown语法