首页 > 其他分享 >【CodeChef】Origin(数论)

【CodeChef】Origin(数论)

时间:2024-05-16 14:52:00浏览次数:27  
标签:Origin lfloor frac 数论 sum rfloor cdot bmod CodeChef

题目大意:

\(f(x)=\begin{cases} x,1\le x\le9\\ f(x的各数位之和),x>9\\ \end{cases}\)

求\(\sum_{i=1}^{n}f(i)\)。


根据打表找规律,我们会发现\(f(x)=(x-1)\bmod 9+1\)。

所以\(\sum_{i=1}^{n}f(i)\)
\(=\sum_{i=1}^{\lfloor\frac{n}{9}\rfloor\cdot 9}f(x)+\sum_{i=\lfloor\frac{n}{9}\rfloor\cdot 9+1}^{n}f(x)\)
\(=\lfloor\frac{n}{9}\rfloor\cdot\sum_{i=1}^{9}f(i)+\sum_{i=1}^{n\bmod 9}f(i)\)
\(=\lfloor\frac{n}{9}\rfloor\cdot\sum_{i=1}^{9}i+\sum_{i=1}^{n\bmod 9}i\)
\(=\lfloor\frac{n}{9}\rfloor\cdot\frac{(1+9)\times9}{2}+\frac{(1+n\bmod 9)*(n\bmod 9)}{2}\)
\(=\lfloor\frac{n}{9}\rfloor\cdot 45+\frac{(1+n\bmod 9)*(n\bmod 9)}{2}\)

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll N=1e6+10,inf=1e18+10,mod=1e9+7;
int main(){
	int T;
	cin >> T;
	while(T--){
		ll n;
		cin >> n;
		cout << n/9*45+(1+n%9)*(n%9)/2 << endl;
	}
	return 0;
}

标签:Origin,lfloor,frac,数论,sum,rfloor,cdot,bmod,CodeChef
From: https://www.cnblogs.com/alric/p/18195884

相关文章

  • [数论] 二项式反演
    菜就多练,输不起就别玩,不会就是不会。二项式推论\(1.\)\(\tbinom{n}{m}=\tbinom{n}{n-m}\)\(2.\)\(\tbinom{n}{m}=\frac{n}{m}\tbinom{n-1}{m-1}\)\(3.\)\(\sum\limits_{i=0}^nC_n^i=2^n\)证明:拆\((1+1)^n\)\(4.\)\(\sum\limits_{i=0}^n(-1)^iC_n^i=0\)特殊的,......
  • Origin2022中文版绘制套娃式柱形图,大柱套小柱!
    柱形图是科研中常用的图表之一,为了同时展示分数据与总数据之间的趋势分布,我们可以采用大柱形图(总数据)嵌套小柱形图(分数据)的展示方式,使图表更清晰直观,下面给大家分享如何制作套娃式柱形图;操作步骤:1、先打开Origin2022软件,然后在Book1中输入如下示例数据:2、选中A-D列的数据:......
  • [数论] 原根
    书接上回...我们知道,我们在使用FFT时,靠的是单位根\(\omega\)。数学家证明这是复数域中唯一符合条件的数。可是它的浮点误差和带来的巨大运算时间使我们有点不能接受。于是,我们想想能不能找个替代品替代掉\(\omega\)。于是,原根就出现了!原根的引入阶对于一个数\(x\),在......
  • 2024ICPC武汉邀请赛-G.Pack-数论分块、整除运算相关的不等式
    link:https://codeforces.com/gym/105143Groupcontests:https://codeforces.com/group/DWEH34LQgT/contest/521901题意:有\(n\)件\(A\)物品,\(m\)件\(B\)物品,两种物品价值分别是\(a,b\),若干件\(A\)和若干件\(B\)可以打包成一个商品,打包尽可能多的商品的情况下让剩余的......
  • LeetCode 2060. Check if an Original String Exists Given Two Encoded Strings
    原题链接在这里:https://leetcode.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/description/题目:Anoriginalstring,consistingoflowercaseEnglishletters,canbeencodedbythefollowingsteps:Arbitrarily split itintoa sequ......
  • [学习笔记] 乘性函数 - 数论
    [SDOI2012]Longge的问题我们要求\(\sum\limits_{i=1}^n\gcd(i,n)\),但\(gcd\)没啥卵用,所以尝试给这n个正整数分组。对于\(gcd(i,n)=1\)的数给他们归到\(G(1)\)这个集合里去,当然,这个集合元素的数量为\(\phi(n)\)。对于\(gcd(i,n)=2\)的数归到\(G(2)\)这个集合里去......
  • [数论] 复数
    从小学我们就知道\(i=\sqrt{-1}\)。复数一般写作\(a+bi\)复数四则运算加法:\((a+bi)+(c+di)=(a+c)+(b+d)i\)减法就是取个相反数。乘法:\((a+bi)\times(c+di)\)\(=ac+(ad+bc)i+bd\timesi^2\)\(=(ac-bd)+(ad+bc)i\)共轨复数\(a+bi\)的共轨复数是\(a-bi\),它们相......
  • 数论进阶
    数论进阶原根与阶阶若\(a,p\)互质,定义\(a\)在模\(p\)意义下的阶为最小的正整数\(t\)满足\(a^t\modp=1\)。\(a\)在模\(p\)意义下的阶记作\(ord_p(a)\),\(a^{ord_p(a)}\modp=1\)。对于整数\(k\),\(a^k\equiv1(\modp)\)当且仅当\(ord_p(a)|k\)。计算......
  • [学习笔记] 质数与唯一分解定理 - 数论
    素性测试素性测试就是判断某个数是否为质数。费马小定理内容:若\(p\)为质数,\(a\)为任意整数,有\(a^{p-1}\equiv1(mod\p)\)那么可以多次随机取一个基数\(a\in(1,p)\)若\(p\)满足上式,那么它为质数的可能性就越大。MillarRabin素性测试inlinellqpow(lla,lln,ll......
  • 数论
    数论常见筛法对于任意正整数\(A\),存在唯一集合{\((p_1,q_1),(p_2,q_2),\dots,(p_n,q_n)\)}满足\(A=\prod^n_{i=1}{p_i}^{q_i}\)\(\min(a,b)+\max(a,b)=a+b\)\(\gcd(a,b)\times\operatorname{lcm}(a,b)=ab\)埃氏筛在\(O(n\log\logn)\)时间内预处理出\([1,n]\)内所......