UVa927 - Integer Sequences from Addition of Terms(數論 Math theorm)

題目大意：

有一個數列，有三種模式，分成 a,b,c，index 從 0 開始，且有一個數字 d，a 為主要的數列，b 數列的方式是重複 \(a_i\) 的數列 \(i * d\) 次，而 c 則是一個 hash 的數列，公式如下
\(a_n = c_0 + c_1 n + c_2 n^2 + … + c_i n*i\)，注意，這裡的 n 是第 n 項，而非 sigma 的意思。

給你 c 數列與 d，還有一個數字 k，詢問 \(b_k\) 的位置？

題目連結

重點觀念

• 了解題目意思，懂得基本數學觀念
• 善用數學的等差公式概念

分析：

我們主要的目的是要找出 \(b_k\) 的位置，由於 b 數列會隨著 d 遞增，但 b 會重複 \(a_i\) 的數列，因次我們要先找出 \(a_i \)，但題目只給我們 c，因此我們要用 c 去推 a，這時候題目的公式就派上用場了。

那現在我們要找出的就是 \(b_k\) 是用到 a 的那個數值了。

怎麼找？

透過等差公式。

由於b 數列的方式是重複 \(a_i\) 的數列 \(i * d\) 次，與等差數列的概念吻合，因此我們進行疊代，找到一個數值(定義 p)可以 \(\geq k\)，再將 p 去套入公式即可，這裡的 p 是公式的 n。

需要特別注意的是那條最長的數列，第一個為數列長度，然後 index 從 0 開始。

參考來源

UVa 927 - Integer Sequences from Addition of Terms - 小白菜又菜

心得

肯定是我的英文太弱才讓我看英文的數學題讓我這麼痛苦QQ，一開始的我把 n 理解為最後一項，害我整個程式都寫錯，看別人的 uva 詳解我才知道這題要怎麼解，題目意思是如何，表示我對英文的數學理解力還不夠。

再多刷些 uva 題目增強八。

我還將那條最長的數列以為全部都是數列的值，都用 stringstream 去解..，後來才發現第一項是 n，index 從 0 開始，嗚嗚。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define MAXN 10020
#define int long long
#define LOCAL
using namespace std;
int C, d, k, temp1, clen; //clen = c 數列 length
int c[MAXN], a[MAXN]; //數列 c 與數列 a

int solve(){
    int x = d, y = 0, p = 0 ; //y 為 a_i，p 判斷當前等差數列的最大長度
    // x 則是下底
    while(p < k){ //如果當前等差數列的最大長度還沒有大於 k 就繼續
        y++; //累加，進行疊代。
        p = y * (d + x) / 2; //等差數列公式
        //cout << "p is" << p << '\n';
        x += d; //下底加大

    }
    //cout << "y is " << y << '\n';
    int ans = c[0], cnt = y;  //cnt 計算 n * i 的倍數
    //ans 是答案，由於第一項不乘以 n，且題目 k 最小為 1，因此我設定第一項是最小答案
    for(int i = 1; i <= clen; i++ ){
        ans += c[i] * cnt; //題目公式
        //cout << c[i] << ' ' << cnt << '\n';
        cnt *= y;
    }
    return ans;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> C;
    while(C--){
        cin >> clen; 
        for(int i = 0; i <= clen; i++) cin >> c[i]; 
        cin >> d >> k;
        cout << solve() << '\n' ;
    }
    return 0;
}