CodeForces - 1469D - Ceil Divisions (思维+数学)

简介: 笔记

Ceil Divisions


题意

3.png

思路

4.png

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
using namespace std;
typedef  long long LL;
typedef pair<int, int>PII;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
const int N = 200010;
int n;
int a[N];
vector<int>v;
void solve() {
  cin >> n;
  v.clear();
  int cnt = 0;
  if (n <= 32) {
    for (int i = 3; i < n; ++i) {
      v.push_back(i);
      v.push_back(i + 1);
      cnt++;
    }
    int t = n;
    while (t != 1) {
      //printf("%d %d\n", n, 2);
      v.push_back(n);
      v.push_back(2);
      cnt++;
      t = ceil(double(t / 2.0));
      //cout << "t == " << t << endl;
    }
  }
  else {
    int x = ceil(pow(n, 1.0 / 5.0));
    for (int i = 3; i < n; ++i) {
      if (i != x) {
        //printf("%d %d\n", i, i + 1);
        v.push_back(i);
        v.push_back(i + 1);
        cnt++;
      }
    }
    int t = n;
    while (t != 1) {
      //printf("%d %d\n", n, x);
      v.push_back(n);
      v.push_back(x);
      cnt++;
      t = ceil(double((t * 1.0) / (x * 1.0)));
    }
    t = x;
    while (t != 1) {
      //printf("%d %d\n", x, 2);
      v.push_back(x);
      v.push_back(2);
      cnt++;
      t = ceil(double(t / 2.0));
    }
  }
  cout << cnt << endl;
  for (int i = 0; i < v.size(); ++i) {
    printf("%d ", v[i]);
    if (i & 1)cout << endl;
  }
}
int main() {
  int t; cin >> t;
  while(t--)
    solve();
  return 0;
}
目录
相关文章
|
4月前
|
算法
Plant(快速幂+数学分析(没想到吧,数学无处不在))
Plant(快速幂+数学分析(没想到吧,数学无处不在))
64 0
|
机器学习/深度学习 人工智能
数学问题之(矩阵快速幂)
数学问题之(矩阵快速幂)
|
人工智能
Codeforces1491——C.Pekora and Trampoline(差分思维+树状数组)
Codeforces1491——C.Pekora and Trampoline(差分思维+树状数组)
104 0
Codeforces1491——C.Pekora and Trampoline(差分思维+树状数组)
|
算法
数学知识:中国剩余定理
复习acwing算法基础课的内容,本篇为讲解数学知识:中国剩余定理,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
178 0
数学知识:中国剩余定理
|
算法
数学知识:快速幂
复习acwing算法基础课的内容,本篇为讲解数学知识:快速幂,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
89 0
数学知识:快速幂
|
存储 算法 图计算
数学知识:容斥原理
复习acwing算法基础课的内容,本篇为讲解数学知识:容斥原理,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
118 0
数学知识:容斥原理
|
算法
数学:扩展欧几里得算法模板
扩展欧几里得算法
95 0