ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 简单
  4. 正文

[ABC233]E - Σ[k=0..10^100]floor(X/10^k)(数学 + 高精度)

2022年4月8日 1091点热度 0人点赞 0条评论

题目传送门:E - Σ[k=0..10^100]floor(X/10^k) (atcoder.jp)

题目大意

顾名思义,求这么一坨东西。

思路

看到这个数据肯定要想用高精度。

而且不能用暴力算法去算这个东西,要想一个O(N)复杂度可以解决的,这就要去找规律了。

我们将所有要加起来的东西竖着写,会得到一个“阵”,暂且叫数阵吧。

这个数阵是沿着副对角线对称的,而每一位上(比如个位,十位)的和,是有递推关系的,可以考虑从后往前(从个位到最高位),以此加入到高精度数组中,再进行一次进位后输出。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 10, N = 1e6 + 5;
int a[maxn], pa = 0;

signed main()
{
	string s;cin >> s;
	int sum = 0;
	for(auto& i : s)sum += i - '0';
	int len = s.length();
	for(int i = len - 1;i >= 0; -- i)
	{
		a[++ pa] = sum;
		sum -= s[i] - '0';
	}
	for(int i = 1;i <= N; ++ i)
	{
		if(a[i] > 9)
		{
			a[i + 1] += a[i] / 10;
			a[i] %= 10;
		}
	}
	for(int i = N, f = 0;i >= 1; -- i)
	{
		if(a[i]) f = 1;
		if(f)printf("%lld",a[i]);
	}
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder C++ 数学 算法竞赛 高精度
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号