[传智杯 #5 初赛] E-梅莉的市场经济学

题目背景

梅莉这个学期选修了经济学。但是主修心理学的她实在不擅长经济领域的分析，为此她时常抱怨自己学不会，想退课。

但是如果现在退掉的话这学期的学分就不够啦，因此她根据“梦中”的经历，“胡诌”了一个简单到不现实的市场模型，并依据这个模型编起了 essay。为了方便地编出图表，她需要写一个程序来查询每个时刻的市场贸易差。

题目描述

市场每一天的贸易差可以视为一个有周期性规律的数列\(a\)： \(\color{red}[0],\color{blue}[0,1,0,-1,0],\color{red}[0,1,2,1,0,-1,-2,-1,0],\color{blue}[0,1,2,3,2,1,0,-1,-2,-3,-2,-1,0]\dots\) 具体而言，\(a\) 可以被分为无穷段，第 \(i\) 段的内容为 \(\{0,1,\cdots,i,i-1,\cdots,0,-1,\cdots,-i,-i+1,\cdots 0\}\)。如下图所示，是将 \(a\) 数列内的前一些点绘制在坐标轴上的情况：

现在梅莉对市场发起了 \(q\) 次询问，每次她会给定一个 \(k\)，希望求出 \(a_k\) 是多少。

输入格式

• 第一行有一个正整数 \(q\)，表示询问次数。
• 接下来 \(q\) 行，每行一个正整数 \(k\)，描述每次询问。

输出格式

• 输出共 \(q\) 行。对于每次询问，输出对应的结果。

样例 #1

样例输入 #1

9
1
10
100
1000
10000
100000
1000000
10000000
100000000

样例输出 #1

0
1
6
-9
-11
-128
406
1629
5154

提示

对于所有数据，\(1 \leq q \leq 10^5\)，\(1 \leq k \leq 4\times 10^{18}\)。

分析

1. 每组共有\(4*i-3\)个数，数列求和 \(\sum_{i = 1}{(4*i-3)}=2*n^2-n\)
2. 二分可以算出\(k\)所在的组
3. 根据k所在的组内的位置可以推测出对应的数,注意下标

代码

#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair <int,int> pii;
const int N=2e9;
ll q,k;
int main(){
    cin>>q;
    while (q--)
    {
        cin>>k;
        ll low=1,high=2e9;
        while (low<high)
        {
            ll mid=(low+high)/2;
            ll now_gp=2*mid*mid-mid;
            if(k<=now_gp){
                high=mid;
            }else{
                low=mid+1;
            }
        }
        ll pre_gp=2*(low-1)*(low-1)-(low-1);
        k-=pre_gp;
        ll now_gp=4*low-3;
        if(k<=now_gp/2){
            if(k<=now_gp/4){
                cout<<k-1<<endl;
            }else{
                cout<<now_gp/2+1-k<<endl;
            }
        }else{
            if(k<=(now_gp/4+now_gp/2+1)){
                cout<<now_gp/2+1-k<<endl;
            }else{
                cout<<k-now_gp<<endl;
            }
        }
        
    }
    
    return 0;
}