首页 > 其他分享 >AT_arc111_a 题解

AT_arc111_a 题解

时间:2023-09-28 19:13:06浏览次数:57  
标签:lfloor 10 right arc111 题解 bmod long ans

洛谷连接&Atcoder 链接

题目简述

给定两个数 \(n\) 和 \(m\),输出 \(\left\lfloor\frac{10^n}{m}\right\rfloor \bmod m\) 的值。

数据范围:\(n \le 10^{18},m \le 10^4\)

思路

首先看到数据范围还是很大的,直接快速幂会炸,所以需要一些优化操作。

推理如下:

\[\left\lfloor\frac{10^n}{m}\right\rfloor \bmod m \equiv \left\lfloor\frac{10^n}{m}\right\rfloor - k \times m \bmod m \equiv \left\lfloor\frac{10^n - k \times m^2}{m}\right\rfloor \bmod m \equiv \left\lfloor\frac{10^n \bmod m^2}{m}\right\rfloor \bmod m \]

经过以上推理,可以发现,仅需用快速幂求 \(10^n \bmod m^2\) 的值即可,时间复杂度 \(O(\log n)\),可以通过。

其中快速幂的代码可以用循环实现(本人觉得比较好用)。

long long qpow(long long a, long long b, long long p) {
	long long ans = 1;
	while(b) {
		if(b & 1) ans *= (a % p), ans %= p;
		a = (a * a % p);
		b /= 2;
	}
	return ans;
}

解决快速幂后,此题就非常简单了,代码如下:

#include<iostream>
using namespace std;

long long n, m, ans = 0;

long long qpow(long long a, long long b, long long p) {
	ans = 1;
	while(b) {
		if(b & 1) ans *= (a % p), ans %= p;
		a = (a * a % p);
		b /= 2;
	}
	return ans;
}

int main() {
	cin >> n >> m;
	cout << qpow(10, n, m * m) / m << endl;
	return 0;
}

AC 记录

\[\texttt{The end!} \]

标签:lfloor,10,right,arc111,题解,bmod,long,ans
From: https://www.cnblogs.com/So-noSlack/p/17736361.html

相关文章

  • AT_agc019_b 题解
    洛谷链接&Atcoder链接。题目简述给定一个字符串\(A\),可以选择区间\([i,j]\)翻转一次,求能得到多少本质不同的字符串。(\(A\)的长度不超过\(2\times10^5\))。思路首先解释本质不同的含义,即不完全相等的两个字符串(可能\(A\)是\(B\)的字串)。如果想直接求得答案显然是不......
  • P1989 无向图三元环计数 题解
    P1989无向图三元环计数题解考虑对无向图的边定向:对于每一条无向边,度数小的点向度数大的点连边,如果读书相等则按编号大小确定。这样枚举一个\(u\),再枚举它的出点\(v\),接着枚举\(v\)的出点\(w\),如果存在一个\(w\),\(u\)向它连边,那么\((u,v,w)\),就对应了原图中的一个三......
  • SOJ1835 题解
    题意给出一个\(1,\dots,n+1\)的排列\(v_{1},\dots,v_{n+1}\)与两组权值\(a_{1,\dots,n},b_{1,\dots,n}\)。满足\(v_{n+1}=n+1\)。构造一张\(n+1\)个点的有向图:对于\(i=1,\dots,n\),从\(i\)向\(i+1\)连一条权值为\(a_i\)的边;对于\(i=1,\dots,n\),找到最小的\(i......
  • LOJ 6479 [ICPC World Finals 2017] 小小水管工 Son of Pipe Stream 题解
    更好的阅读体验题意原题链接给出\(n\)个城市和\(m\)条双向管道,以及两个实数\(v\)和\(a\)。有两种液体,分别是水和Flubber(下面简写为W和F)。\(1\)号和\(2\)号城市分别生产Flubber和水,并通过管道流入\(3\)号城市。对于一条管道,其中可以同时存在两种液体,但是方向......
  • Jenkins问题解决_控制台输出:Windows下中文乱码,文本方式查看显示正常
    背景使用Git克隆代码时出现错误,控制台输出内容为中文乱码,文本方式查看显示正常Jenkins版本:2.423原因Jenkins内JAVA编码设置问题查看jenkins编码格式系统管理——>系统信息,查找sun.jnu.encoding字段。如果不是UTF-8,就可能导致中文支持有问题(GBK等支持度不够)。解决设......
  • 题解 [HEOI2016/TJOI2016] 排序
    题目链接看到这道题按照套路首先想到二分答案(即二分\(q\)位置上的数,记作\(mid\))。再按照套路将大于\(mid\)的数字设为\(1\),将等于\(mid\)的数设为\(2\),小于\(mid\)的数字设为\(0\)。那么对于区间\([l,r,0]\)操作,应该先讲\(0,1,2\)的数量找出来,然后按照从小到大......
  • 题解 CF1873H【Mad City】
    其他题解怎么又Tarjan又Dijkstra的,这是div4H的样子吗,来个简单好写的做法。题面里的人名太复杂了,本题解中称为警察和小偷。注意到,如果小偷成功到达了环上,那么一定不会被警察抓到。因为小偷知道警察下一步会走到哪里,他可以执行相同的操作(顺时针/逆时针/静止),使得他和警察之间......
  • [ARC124C] LCM of GCDs 题解
    题面给定\(N\)个正整数对\((a_i,b_i)\)和两个初始为空的集合\(S,T\),你可以选择将每个数对的两个元素划分到两个不同的集合中。求\[\max\operatorname{lcm}(\gcd\limits_{x\inS}x,\gcd\limits_{y\inT}y)\](\(1\leN\le50,1\lea_i,b_i\le10^9\))。题解首先,......
  • P4370 [Code+#4] 组合数问题2-题解-有关对数的小技巧
    20230927P4370[Code+#4]组合数问题2-solStatement传送门给你两个数\(n,k\),要求对于组合数\(C_{a}^{b}\)找到任何\(k\)个,让他们的和最大,且组合数各不相同,当且仅当\(a,b\)不完全相同时,组合数不同。Solution首先,很容易发现\(C_{n}^{m}\gtc_{n-1}^{m}\),所......
  • CF364D Ghd 题解
    CF364DGhd题解题目大意给定一个长度为\(n\)的序列,你需要从中选出一个元素个数不少于\(\left\lceil{\frac{n}{2}}\right\rceil\)的子序列,使得这个子序列中所有元素的\(\gcd\)最大。分析数据范围吓人。\(10^6\),但是根本想不到什么\(O(n\logn)\)或\(O(n)\)的算法......