Profile cover photo
Profile photo
Fu Erzheng
3 followers -
宅若旧时自然萌,萌到深处天然呆。
宅若旧时自然萌,萌到深处天然呆。

3 followers
About
Posts

Post has attachment
[UVa 10662] Perfect P-th Powers【质因数分解/欧几里得算法/初等数论】
[Description] 给定一个x(int 范围),求它最多能开多少次方。也就是满足x=y^k的最大k值。 [Solution] 把x质因数分解。令x=p1^k1*p2^k2*…*pn^kn,找到所有k的gcd,所以x=(p1^(k1/gcd)*p2^(k2/gcd)*…*pn^(kn/gcd))^gcd. 可以证明,gcd就是最大的指数了。 需要注意的是x<0的情况,此时gcd必须为偶数(不然幂是正数),这时把gcd中所有的2再放进括号就可以了,也就是说,最后得到的gcd是原值不断除2的结果。 x还是开...
Add a comment...

Post has attachment
[BZOJ 4173]数学【欧拉函数】
/出题人官方题解/ [Description] [Solution] [Code] #include<cmath> #include<cstdio> typedef long long ll; const int mod=998244353; ll Phi(ll x){     ll ans=x;     for(int i=2,lim=sqrt(x)+1;i<lim;i++) if(!(x%i)){    ans=ans/i*(i-1);    while(!(x%i)) x/=i; }     if(...
Add a comment...

Post has attachment
【欧拉定理/初等数论】[BZOJ 3884] 上帝与集合的正确用法
[Description]求值 [Solution] 不要被无限个2吓到了,这一题有一些有趣的性质可以发掘的。 这里介绍两个解法。 · Solution 1 我们温习一下欧拉定理: 和它的推广: 我们发现,这题的n,p并不一定互素啊,怎么办呢?我们可以让他们强行互素。 利用公式: 我们把原题中的p分为2^k+y 所以原式化为 此时y是奇数,和指数互质了!然后就可以愉快地使用欧拉定理--原式化为 我们发现中间的指数一部分又与原问题相似,于是想到可以递归求解。 那边界是什么呢?我们发现,phi(y)会不断缩小,而...
Add a comment...

Post has attachment
【Lucas定理/费马小定理/中国剩余定理/扩展欧几里得】[BZOJ 古代猪文]
[Description] 求 [Solution] 容易得到, 所以,重点在怎么求求 如果是p-1是个质数,我们可以用sqrt(n)的时间枚举所有d,用Lucas定理分别计算求和即可。 但是我们发现p-1=2*3*4679*35617,并不是一个质数,所以Lucas定理不能用了吗?并不,我们可以算出这个合式分别对2、3、4679、35617的模值,写出四个同余方程,再用孙子定理求解即可。注意特判g==p的情况,此时费马小定理不成立,ans=0. [Code] #include<cmath> #include...
Add a comment...

Post has attachment
【莫比乌斯反演/容斥原理/分块】[BZOJ 2301] Problem b
[Description] 有n个询问(n ≤ 50000),每个询问有五个整数a,b,c,d,k, 求有多少个数对 (x,y) 满足 a ≤ x ≤ b , c ≤ y ≤ d, 且 gcd(x,y)=k. (a ≤ b ≤ 50000,c ≤ d ≤ 50000,k ≤ 50000) [Solution] 我们发现,计算一个数x在某个闭区间[a,b]内的因数数量并不是很方便,可以转化为x在区间[1,b]的因数的数量-x在区间[1,a-1]的因数的数量(因为求[1,Z]比较好求)。 原问题是,对于所有x∈[...
Add a comment...

Post has attachment
[Codeforces Round #309 (Div. 2)] #ABC题解
没想到时隔两天竟然又打了cf,做了3题就弃疗了。 题目链接: Codeforces Round #309 (Div. 2) A. Case of Zeros and Ones [Description] 给定一个01串,相邻的0和1可以消掉,问最终这个串最短可以消到多长。 [Solution] 可以证明,当这个序列0和1都还存在,是可以继续进行消除的,直到某个数字没有。 [Ans] n-2*(min(num0.num1)) [Code] #include<cstdio> #include<cctype> #i...
Add a comment...

Post has attachment
【莫比乌斯函数/容斥原理/二分法】[BZOJ 2440] 完全平方数
[Description] 求第k个无平方因子数。无平方因子数指分解之后所有质因数的次数都为1的数。 [Solution]  我们可以进行二分操作,查找区间[1,x]里有几个无平方因子数,逐渐缩小范围依次求解。  然而怎么计算区间[1,x]内无平方因子数的个数Q呢?  根据容斥原理,  Q=x-x内有一个平方因子的数+x内有两个平方因子的数-x内有三个平方因子的数…  =x-x内(4的倍数个数+9的倍数的个数+25的倍数的个数)+x内(36(2*3*2*3)的倍数+100(2*5*2*5)的倍数)…  =  ...
Add a comment...

Post has attachment
[Codeforces Round #309 (Div. 2)] #ABC题解
鉴于本人水平有限,两小时只A了三道,剩下的又不想看了,无聊写写前三题题解。 A. Kyoya and Photobooks [Description] 给定一个只有小写字母的字符串,可以在任意位置插入任意一个小写字母,求得到的字符串种数。 [Solution] 枚举+哈希水题 [Code] #include<map> #include<string> #include<iostream> using namespace std; map<string,bool> M; int main(){ int ans=...
Add a comment...

Post has attachment
[Codeforces Round #309 (Div. 2)] 酱油记
这是人生第一次打codeforces啊...前前后后发生了很多事,手一抖又写了篇Blog. ...其实前几天就有所准备,昨天晚上大约7点才发现当晚有比赛qwq,租的房子又没网==,只能凌晨待在学校打啊!!!瞬间大家就就纷纷打电话回家说今晚不回去了==然后有家长打电话给cy问了问情况,然后那个爆炸啊==,cy勒令我们回家,还扬言要到学校来抓人--,然后我们就决定在机房关灯锁门,装作不在==还花了半个小时堵了门。 结果cy始终没来--中间xyx和一个学校领导莫名来了机房==吓得我们一跳一跳,始终不是个办法啊==于...
Add a comment...

Post has attachment
[数学小考] 2015.6.24
考了三道比较简单的数学题(题目来源网络) 傻牛的约数研究 (divisor) [ Description ] 傻牛最近在研究约数,它觉得这玩意很牛逼。 首先,对于一个数字 X 来说,设 F(X) 表示 X 的约数个数,可以先将 X 表达成为若干个质数的幂次 之积,即 X=p1k1*p2k2 * …… psks ,然后 F(X)=(k1+1)(k2+1)* …… *(ks+1) 。傻牛觉得 这个碉堡了。有一天它想,我们是不是可以求出 F(1)+F(2)+F(3)+ …… +F(N) 的值呢?结果,它 晕掉了...
Add a comment...
Wait while more posts are being loaded