数论2️⃣

sccc_ · 2024-07-10 22:16:13 · 个人记录

是的 又起猛了 又学数论了
比昨天更country了
为什么老师让我们学数论呢 因为他善

步入正题

P9825 [ICPC2020 Shanghai R] Fibonacci

不知大家知不知道 斐波那契数列是有规律的
每三个数 他们的奇偶性分别是：鸡鸡呕
那么如果是鸡乘呕 那就是奇数的个数 偶数的总数 如果是呕乘呕 那就是偶数的个数 （偶数的个数 - 1） / 2

#include <bits/stdc++.h>
using namespace std;

#define int long long
int f[1000005], ans;

signed main()
{
    int n;
    cin >> n;
    int tmp = n / 3;
    cout << (tmp * (tmp - 1) / 2) + (tmp * (n - tmp));
    return 0;
} 

B3752 [信息与未来 2019] 新斐波那契数列
这道题推一下规律我们能发现

• f_1 = 1 + 0a
• f_2 = 0 + 1a
• f_3 = 1 + 1a
• f_4 = 1 + 2a
• f_5 = 2 + 3a
• f_6 = 3 + 5a

  可以发现 一个算式里的两个加数都是斐波那契数列
  所以维护f_i为斐波那契数列里的第i项

  
  #include <bits/stdc++.h>
  using namespace std;

int t, a[1000005], b[1000005];

void work() { int n; cin >> n; for (int i = 2; i <= 50; i ++) { if (n < a[i] or n < b[i]) continue; if ((n - a[i]) % b[i] == 0) cout << i << ' ' << (n - a[i]) / b[i] << endl; } }

signed main() { a[1] = b[2] = 1; a[2] = b[1] = 0; for (int i = 3; i <= 50; i ++) a[i] = a[i - 1] + a[i - 2], b[i] = b[i - 1] + b[i - 2]; cin >> t; while (t --) { work (); } return 0; }

[P9748 [CSP-J 2023] 小苹果](https://www.luogu.com.cn/problem/P9748)  
这道题是斐波那契数列改编的 和斐波那契数列的特点很像 都是鸡鸡呕  
那这一堆苹果里我们就要拿$ceil(n/3.0)$个  
![](https://cdn.luogu.com.cn/upload/image_hosting/f64p93id.png)
假如有12个苹果  
那么第一次我们用魔力把$1,4,7,10$ 个苹果变成诺基亚  
那么还剩$2,3,5,6,8,9,11,12$  
第二次把$2,6,11$变了  
还剩$3,5,8,9,12$  
第三次变$3,9$  
还剩$5,8,12$  
第四次变$5$  
还剩$8,12$  
第五次变$8$  
还剩$12$ 那么他是这三个数中的第一个数  
所以 当$n % 3 == 1$时就可以取到最后一个诺基亚  
```c++
#include <bits/stdc++.h>
using namespace std;

int n, d1, d2;

signed main()
{
    cin >> n;
    for (int i = 1; i ; i ++)
    {
        if (n == 0)
            break;
        if (!d2 and n % 3 == 1)
            d2 = i;
        n -= ceil (n / 3.0); 
        d1 ++;
    }
    cout << d1 << ' ' << d2;
}