[C++知识库] 【蓝桥杯】分数

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 【蓝桥杯】分数 -> 正文阅读

[C++知识库]【蓝桥杯】分数

作者:recommend-item-box type_blog clearfix

穿越隧道

可以用等比数列或者模拟分数之间的相加

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
ll a[N];//分母
ll fz[N];
int main()
{
  a[1] = 1;
  for(int i = 2; i <= 20; i++){
    a[i] = a[i-1]*2;
//	printf("[%d]=%d\n",i,a[i]);
  }
  for(int i = 1; i <= 20; i++){
  	fz[i] = 1;
  }
  for(int i = 2; i <= 20; i++){
    fz[i] = fz[i - 1] * a[i] + fz[i] * a[i - 1];
    a[i] = a[i - 1] * a[i];
    ll gcdd = __gcd(fz[i],a[i]);//会爆int 
    fz[i] /= gcdd;
    a[i] /= gcdd;
//    printf("i = %d, fz[%d]=%d,a[%d]=%d\n",i,i,fz[i],i,a[i]);
  }
  cout << fz[20] <<"/" << a[20] << endl;
  //等比数列公式
  //Sn = a1(1-q^n)/(1-q)=2 - 1/(2^19) 
  //通分:Sn = (2^20 - 1) / (2^19) 
//  cout << (int)pow(2,20) - 1 <<"/"<< pow(2,19) << endl; 
//   cout << (1 << 20) - 1 <<"/" << (1 << 19) << endl;
  return 0;
}