Doraemon's Blog

欧几里得定理其实就是求gcd的辗转相除法，gcd(a,b)==gcd(a-b,b)，由此可以把a中的b全部拿掉，gcd(a,b)==gcd(a%b,b)， ~a是大于b的~gcd(a,b)==gcd(b,a%b) 欧拉函数具体证明点击我X(N)==N (1/p1) (1/p2) (1/p3) … *(1/pn)(pi为N的质因子) 性质 对于任意一个质数 p ,φ(n)=n−1 因为n为质数,与他互质的个数就是 n-1 当 gcd(n,m)=1时,φ(nm)=φ(n)φ(m) 因为φ(n)是积性函数。 积性函数指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。 若 n=p^k^ 其中p为质数,则φ(n)=p^k^−p^k−1^=(p−1)p^k−1^ 1→n中除了p的倍数，都与p^k^互质,1→n中p倍数的个数为 p^k^÷p=p^k−1^ 所有小于n与n互质个数的和sum=n × φ(n)/2 推导点击我 如果 i mod p=0,其中p为质数,则 φ(i ∗ p)=p ∗ φ(i),否则φ(i ∗ p)=(p−1)φ(i) n=∑d|nφ ...

以下题目涉及知识有 欧拉函数、素数筛、算数基本定理（唯一分解定理） 因为数论之前没咋学，欧拉函数还是这两天补的，又要考试，时间不够，所以大多数都是直接搜题解做的，本来信誓旦旦好好写一些题解巩固一下的，发现越写越累，索性直接搬来别人的优质题解算了🤔 一定记得素数筛时isp数组要用bool，bool只占用一个字节，int4个会爆内存，卡死我了，我说咋一直爆内存 Bi-shoe and Phi-shoe题意：给定N个数，让你求欧拉函数值大于等于这N个数的的那个数的最小数值之和（这里1的欧拉函数值很特殊，设置为0，因为小于1且与1互质的数量为0）例如：N==21 2则答案为4 == 1+3思路要求的是欧拉函数值大于等于给定数的最小数，那么我们就要让这个数对应的欧拉函数值尽可能大一点，什么情况下一个数的欧拉函数值最大呢？很明显是素数时！一个素数的欧拉函数值就等于这个数减一，从这里我们就能推出来最小的那个对应欧拉函数值~大于等于~给定数的那个数最小就是这个给定数后面的那个素数，例如： 10对应的就是11 ，12对应13 ，14对应17，11，13，17就是所要求的最小的三个数，由此思路就明 ...

今天有些疲倦，不想学习，就去网上学习做了一个小游戏，如果你是网友，没接触过图形库，要先安装esayx库，网上有许多，在这里不贴了，素材地址： https://pan.baidu.com/s/1GWnLePCiLcxlJHOaBKEeaA 密码：pmzq 💪 成品视频: Here 希望该文章能帮助到您 不要白嫖了！！！留下您的评论吧 谁能帮我测试一下下面的赏是不是出错了😘 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413 ...

发现了一些快速幂上的小问题，可以说很细节的问题了，导致我第一题巨水的一道题wrong了5次！！当时都懵了，感觉代码一点毛病都没有🐷（菜是原罪） 把这次我在快速幂模板上踩的坑说一下，看下面两段代码 12345678910111213141516代码一ll qpow(ll a,ll b){ if(b==0) return 1; ll ans=qpow(a,b>>1)%MOD; ans*=ans%MOD; if(b&1) ans*=a%MOD; return ans%MOD;}代码二ll qpow(ll a,ll b){ if(b==0) return 1; ll ans=qpow(a,b>>1)%MOD; ans=ans*ans%MOD; if(b&1) ans=ans*a%MOD; return ans%MOD;} 看着这两段代码没啥区别，就是把ans=ans*ans改成了ans*=ans，如果没有取模的话这俩没有任何区别，但是一旦取模就是AC和wrong的天壤之别，为什么？首先看ans*=an ...

PPT上面的好多题都做不了，ACWING上的题要报名才能做，Codeforces 1000C搜不出来，就做了剩下的，不过二维差分前缀和早就掌握了 ACWING-797. 差分超级模板 Code123456789101112131415161718192021#include<bits/stdc++.h>using namespace std;const int MAXN=1e5+100;int val[MAXN],cha[MAXN];int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>val[i]; while(m--){ int l,r,c; cin>>l>>r>>c; cha[l]+=c; cha[r+1]-=c; } for(int i=1;i<=n;i++){ cha[i]+=cha[i-1]; if(i!=n) cout<<val[i]+cha[i] ...

A 前M大的数暴力累加每两组数，再排序输出前M个1234567891011121314151617181920212223242526272829#include<cstdio>#include<set>#include<iostream>#include<algorithm>#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) using namespace std;const int MAXN=3e3+100;int v1[MAXN],v2[5000000];int main(){// ios; int n,m; while(scanf("%d %d",&n,&m)!=EOF){ for(int i=1;i<=n;i++) cin>>v1[i]; int tail=0; for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++)& ...

题目 F - 水果 夏天来了~好开心啊,呵呵,好多好多水果~ Joe经营着一个不大的水果店.他认为生存之道就是经营最受顾客欢迎的水果.现在他想要一份水果销售情况的明细表,这样Joe就可以很容易掌握所有水果的销售情况了. Input 第一行正整数N(0

唯一一场每道题都有思路的比赛，感觉还行，虽然有思路不代表能AC，不过还是很开心的，因为除了E题的桶没想到外其他都是自力更生做出来的😊 A Sum of Round Numbers分析签到题，就是遍历数的每一位，求出非0的位数有几位，然后int一个v=1，之后没走一个数v*=10，然后当一位数不等于0时就乘上v就行了，这道题用字符串应该更简单，但是我想试试用while，练练手 CODE123456789101112131415161718192021222324252627282930#include<stdio.h>#include<iostream>#include<algorithm>#include<string.h>#define ios ios::sync_with_stdio(0)using namespace std;const int MAXN=1e4+100;int main(){ ios; int t,k; cin>>t; while(t--){ cin>>k; ...

STL next_permutation函数实现原文链接掌握了next_permutation函数的原理:smile:12345678910111213141516171819202122void inline swap(char *s1,char *s2){ char t=*s1; *s1=*s2; *s2=t;}/***反转字符串函数,s,e分别执行字符串的开始和结尾，不能反转中文 **/void reverse(char *s,char* e){ for(e--;s<e;s++,e--)swap(s,e);}bool next_permutation(char *start,char *end){ char *cur = end-1, *pre=cur-1; while(cur>start && *pre>=*cur)cur--,pre--; if(cur<=start)return false; for(cur=end-1;*cur& ...

题目problem link可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。Input输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小NM（1 <= N,M <=10)。T如上所意。接下去的前NM表示迷宫的第一层的布置情况，后NM表示迷宫第二层的布置情况。Output如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。Sample Input15 5 14S#. ...