欧拉定理的应用:Counting regions
欧拉定理的应用：Counting regionsCounting regions
Niuniu likes mathematics. He also likes drawing pictures. One day, he was trying to draw a regular polygon with n vertices. He connected every pair of the vertices by a straight line as well. He counted the number of regions inside the polygon after he completed his picture. He was wondering how to calculate the number of regions without the picture. Can you calculate the number of regions modulo 1000000007? It is guaranteed that n is odd.
在图论里有这样一个定理：
对于 ...
题型整理（3）
余数之和给出正整数 n 和 k，计算 j(n,k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n 的值。
例如j(5,3) = 3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5 = 0 + 1 + 0 + 3 + 3 = 7。
输入格式
输入仅一行，包含两个整数 n,,k。
输出格式
输出仅一行，即 j(n,k)。
数据范围
1≤n,k≤10^9
输入样例
5 3
输出样例
7
思路：
整除分块：
\displaystyle\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor(它喵的，不知道别人网站里的公式可以复制，自己学了半天mathjax语法)
$\lfloor x \rfloor$表示对x向下取整，通过打表可以发现n/i会有多个相等的区间，区间的右端点即为n/(n/i),则整除分块的代码为：
1234for(int l=1,r;l<=n;l=r+1){ r=n/(n/l); ans+=(r-l+1)*(n/l);}
而本题的答案为
ans=n*k-\displays ...
题型整理（2）
古代猪文213. 古代猪文 - AcWing题库数论好题
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include<iostream>#include<cstdio>#include<cstring>#define int long longusing namespace std;const int N = 37000;const int MOD = 999911658;int plist[5] = {0,2,3,4679,35617};int n,q;int a1,a2,a3,a4;int fac[N],a[N];inline int gcd(int a,int b) { if(b == 0) return a; else return gcd(b,a % b);}inline int ...
2022年蓝桥杯省赛C++B组部分题解
试题 A: 九进制转十进制本题总分：5 分【问题描述】九进制正整数2022转换成十进制等于多少？
123456789#include<bits/stdc++.h>using namespace std;int main(){ int t; t=2*pow(9,3)+2*9+2; cout<<t; return 0;}
试题 B: 顺子日期本题总分：5 分【问题描述】小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123； 而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022年份中，一共有多少个顺子日期。
123456789101112131415202201202022012120220122202201232022012420220125202201262022012720220128202201292022101220221123202212302022 ...
题型整理（1)
卡特兰数应用场景：
1.n个节点能组成几种二叉树2.括号匹配给出n对括号，求可以组成的合法表达式的个数3.凸多边形的三角划分4.一个顺序为1~n的进栈序列，有多少种出栈序列
卡特兰数求解代码（从0开始，用的组合数方法求）：
1234567891011121314151617181920212223242526272829303132333435363738394041#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=2e5+10;const int MOD=1e9+7;ll fact[N];ll inv_fact[N];ll qpow(ll x,ll y){ ll base=x,ret=1; while(y){ if(y&1) ret=ret*base%MOD; base=base*base%MOD; y>>=1; } return ret;}void init(){ fact[0]=inv_fact[0]=1; for(int i=1,inv ...
