引言
第一篇博客，用以记录自己学习的过程，欢迎大佬们批评指正，期待更好的算法和更优化的代码。
本篇内容仅供交流学习，读者因其他用途造成的一切后果与本人无关。
Hello world
#includeint main(){//注意大小写和空格printf("Hello World");return 0;}A+B
#includeint main(){int a,b;scanf("%d %d",&a,&b);printf("%d",a + b);return 0;}数据类型大小及范围
#include#includeint main(){int a;scanf("%d",&a);//注意数值和输出类型匹配if( a == 1 ) printf("%d,%d,%d",sizeof(char),CHAR_MIN,CHAR_MAX);if( a == 2 ) printf("%d,0,%u",sizeof(unsigned char),UCHAR_MAX);if( a == 3 ) printf("%d,%d,%d",sizeof(short),SHRT_MIN,SHRT_MAX);if( a == 4 ) printf("%d,0,%u",sizeof(unsigned short),USHRT_MAX);if( a == 5 ) printf("%d,%d,%d",sizeof(int),INT_MIN,INT_MAX);if( a == 6 ) printf("%d,0,%u",sizeof(unsigned int),UINT_MAX);if( a == 7 ) printf("%d,%ld,%ld",sizeof(long),LONG_MIN,LONG_MAX);if( a == 8 ) printf("%d,0,%lu",sizeof(unsigned long),ULONG_MAX);if( a == 9 ) printf("%d,%lld,%lld",sizeof(long long),LLONG_MIN,LLONG_MAX);if( a == 10 ) printf("%d,0,%llu",sizeof(unsigned long long),ULLONG_MAX);return 0;}平均值
#includeint main(){//选择范围较大的数据类型long long a,b;scanf("%lld %lld",&a,&b);printf("%lld",(a + b)/2);return 0;}进制转换
#includeint main(){long long a;scanf("%lld",&a);//X为大写printf("%X,%o",a,a);return 0;}浮点数输出
#includeint main(){double a;scanf("%lf",&a);printf("%.6lf,%.2lf,%.8lf",a,a,a);return 0;}动态宽度输出
#includeint main(){long long m,n,a;int w = 0;scanf("%lld %lld",&m,&n);a = m;//获得m的位数while(a != 0){w++;a = a/10;}if(n > w){for(int i = 1;i <= (n - w);i++){printf("0");}printf("%lld",m);}else printf("%lld",m);return 0;}计算地球上两点之间的距离
#include#include#define PI 3.14159265358979323846#define R 6371int main(){//latitude纬度longitude经度double longi1,lati1,longi2,lati2,dlongi,dlati;double a,d;scanf("%lf %lf\n%lf %lf",&lati1,&longi1,&lati2,&longi2);//注意将角度转化为弧度再进行计算longi1 = longi1 * (PI /180.0);lati1 = lati1 * (PI / 180.0);longi2 = longi2 * ( PI /180.0);lati2 = lati2 * (PI / 180.0);dlongi = longi2 - longi1;dlati = lati2 - lati1;a = pow(sin(dlati / 2),2) + cos(lati1) * cos(lati2) * pow(sin(dlongi / 2),2);d = 2 * R * asin(sqrt(a));printf("%.4lfkm",d);return 0;}风寒指数
%g表示自动舍去小数后不必要的0，整数则直接输出整数
#include#includeint main(){double ws,at,wc;double a,b,c;scanf("%lf %lf",&ws,&at);a = 0.6215 * at;b = 11.37 * pow(ws,0.16);c = 0.3965 * at * pow(ws,0.16);wc = 13.12 + a - b + c;wc = round(wc);printf("%g",wc);return 0;}颜色模型转换
#include#includeint main(){unsigned int R,G,B;double r,g,b,maxi,mini,d;double H,S,V;scanf("%u %u %u",&R,&G,&B);//应先将R，G，B范围转化为（0，1）//转化关系可上网自行搜索，即/255r = R / 255.0;g = G / 255.0;b = B / 255.0;maxi = g;mini = g;if(r > maxi) maxi = r;if(b > maxi) maxi = b;if(r < mini) mini = r;if(b < mini) mini = b;d = maxi - mini;V = maxi;if(V != 0) S = d / maxi;//注意讨论V是否为0else S = 0;if(d != 0){//注意小数尽量不要直接比较（float不能比较，但double与long double型可以）//可以将两数差值与极小数进行比较，判定是否相等//1e-9表示1*10^-9if(maxi - r < 1e-9){H = (g - b) / d;}if(maxi - g < 1e-9){H = 2 + (b - r) / d;}if(maxi - b < 1e-9){H = 4 + (r - g) / d;}H = H * 60;if(H < 0){H+= 360;}}//不要遗漏H可能为0的情况else H = 0;printf("%.4lf,%.4lf%%,%.4lf%%",H,S * 100,V * 100);return 0;}方阵
方法一：思路为以0为分割
左边递减输出，右边递增输出
# include int main(void){int i,n;scanf("%d",&n);for (i=0; i-1;j--){printf(" %d",j);}for(int g=1;g<n-i;g++){printf(" %d",g);}printf("\n");}return 0;}方法二：利用绝对值!(思路来自“rivenkki”）
#include#includeint main(){int a;scanf("%d",&a);for(int i =0;i对称数
此题解法很有意思，是对switch用法很好的诠释。
简单解释一下switch：
我们清楚switch(p)中p为预判定的式子，计算机将自动判断p与case后设定的东西是否相等，但我们需要理解的是case语句只是提供了一个执行switch内语句的接口，这里就涉及到了break的作用。
以此题为例：
若p=0，显然他与case 0相符合，那么这时这个case 0后的语句就将被依次执行，直到遇到了第一个break语句，那么此次switch语句框架结束，立刻退出switch执行 switch外的代码。
若p=6，那则从case 6后开始执行，到第一个break结束并退出switch。
从这篇文章里学习到的：c语言switch中break语句的作用
#includeint main(){int n,p,bn,r = 0;scanf("%d",&n);bn = n;while(bn > 0){p = bn % 10;switch(p){//0，1，8，6，9才可能构成对称数，3，4，7显然不可能构成对称数//另外此题认为2，5，也无法构成case 0:case 1:case 8:r = r * 10 + p;break;//6，9旋转发生变化，因此单独考虑case 6:r = r * 10 + 9;break;case 9:r = r * 10 + 6;break;default:printf("No");return 0;//r = r * + ；的操作是在进行书的翻转//即最后一位变成第一位，倒数第二位变成第二位，以此类推}bn = bn / 10;}if(n == r) printf("Yes");else printf("No");return 0;}乘数模
直接相乘再mod可能会超出数据上限，可分别mod相乘再mod，可自行证明。
#includeint main(){long long a,b,m;scanf("%lld %lld %lld",&a,&b,&m);printf("%lld",(a % m) * (b % m) % m);return 0;}比率
思路为把小数部分乘10^c变为整数后作为分子，再将分母设为10^c进行约分
#include#includeint main(){double n,g;long long fz,fm,d,c=0,b=0,x,tfz,tfm;scanf("%lf",&n);int k = 0;g = n;//求出小数位数cwhile(k != g){g *= 10;k = (int)g;c++;}fm =pow(10,c);fz = n * pow(10,c);tfz = fz;tfm = fm;//获得最大公约数x（‘分数的加减乘除法’中提供了另一种更为简单求法）while(tfz % 2 == 0&&tfm % 2 ==0){tfz /= 2;tfm /= 2;b++;}//更相减损术while(tfz != tfm){if(tfz > tfm) tfz -= tfm;else tfm -= tfz;}x = pow(2,b) * tfz;//进行约分fz /= x;fm /= x;printf("%d/%d",fz,fm);return 0;}分数的加减乘除法
利用递归求m,n的最大公约数(太强了qwq)
注意三点：
1.考虑结果为1时的输出
2.考虑减法分子为0时的输出
3.考虑减法结果为负的输出
#include#include//辗转相除法，可自行代数检验int gcd(int m,int n){if(n == 0) return m;else return gcd(n,m % n);}int main(){long a,b,c,d;long m,n;long t;scanf("%ld/%ld\n%ld/%ld",&a,&b,&c,&d);//加法m = a * d + c * b;n = b * d;t = gcd(m,n);m /= t;n /= t;if(m == n) printf("(%ld/%ld)+(%ld/%ld)=1\n",a,b,c,d);else printf("(%ld/%ld)+(%ld/%ld)=%ld/%ld\n",a,b,c,d,m,n);//减法m = a * d - c * b;n = b * d;t = abs(gcd(m,n));//将最大公约数取绝对值保证结果为负数时，输出的正确性m /= t;n /= t;if(m == 0) printf("(%ld/%ld)-(%ld/%ld)=0\n",a,b,c,d);else if(m == n) printf("(%ld/%ld)-(%ld/%ld)=1\n",a,b,c,d);else printf("(%ld/%ld)-(%ld/%ld)=%ld/%ld\n",a,b,c,d,m,n);//乘法m = a * c;n = b * d;if(m == n) printf("(%ld/%ld)*(%ld/%ld)=1\n",a,b,c,d);else{t = gcd(m,n);m /= t;n /= t;printf("(%ld/%ld)*(%ld/%ld)=%ld/%ld\n",a,b,c,d,m,n);}//除法m = a * d;n = b * c;if(m == n) printf("(%ld/%ld)/(%ld/%ld)=1\n",a,b,c,d);else{t = gcd(m,n);m /= t;n /= t;printf("(%ld/%ld)/(%ld/%ld)=%ld/%ld\n",a,b,c,d,m,n);}return 0;}组合数
#includeint main(){int n,c;scanf("%d",&n);for(int i=0;i<10;i++){for(int j=0;j<10;j++){for(int g=0;g<10;g++){for(int w=0;w<10;w++){if((i+j+g+w)==n) c++;}}}}printf("%d",c);return 0;}级数和
#includeint main(){int n;double t,sum = 0;scanf("%d",&n);for(int i=1;i<n+1;i++){if(i==1){sum = sum + 1.2;printf("1.2");}else if(i<9){t = i + (i+1)/10.0;sum = sum + t;printf("+%g",t);}else if(i<99){t = i + (i+1)/100.0;sum = sum + t;printf("+%g",t);}else{sum = sum + 99.1;printf("+99.1");}}printf("=%g",sum);return 0;}倍数和
方法一：
注意去重，及既能被3整除又能被5整除的数（代码较长，速度较快）
#include//获得小于n的所有自然数中3和5的倍数之和unsigned int sum(unsigned int a){long long h = 0,i=0,j=0,g=0;while((3*i)方法二：
不用去重（代码较短，速度较长）
#includeint main(){long long t;scanf("%lld",&t);unsigned int a[t];for(int i=0;i<t;i++) scanf("%lld",&a[i]);for(int i=0;i<t;i++){long long sum=0;for(int j=1;j幂数模
此题学到很多新东西，初步涉及了一点算法问题
为了避免对a全部幂运算再取模超出数值范围，采取快速模幂运算，用到了二进制指数法和分治算法的思想
以13为例进行简单的说明：
13的二进制表示为1101，正常情况下如果要计算a^13，需进行13次乘法，为了减少计算时间，我们对算法进行优化
13=1×2^3+1×2^2+0×2^1+1×2^0，假设最终结果为r，不难发现，当二进制位数为0时，我们可以先不将r乘2，而是让a自乘（即a=a×a，相当于a^2^n，n每次加1），同时进行向右按位位移1位的操作（即>>=1），那么若右移后的最低位为1，我们便将r乘此时的a，这样就能使得运算次数减少。
详细解释一下，欲求5^13
while(b != 0){//b&1：用来判断当前b的二进制最低位是否为1//若为1，则累乘if(b & 1) t = t * a;//否则，只是将a自乘，并不与最终结果t累乘a = (a * a);//将b向右按位位移1位b >>= 1;}/*初始b=13=（1101）B=2^3+2^2+2^0=8+4+1，a=5，t=1第一次b&1=0001 为真if条件成立 t=t*5=1*5a=a*a=5^2b=110第二次b&1=000 为假if不成立t=1*5不变a=a*a=5^2*5^2=5^4b=11第三次b&1=01 为真if条件成立 t=t*a=1*5*5^4a=a*a=5^4*5^4=5^8b=1第四次b&1=1 为真if条件成立 t=t*a=1*5*5^4*5^8=5^（2^0+2^2+2^3）*/感觉本质就在于把指数分解为二进制
具体操作是通过b&1判断和b>>=1，使得a自乘后的指数和二进制表示中为1的位对应的数相一致
本题答案
#includeint main(){long long a,b,m,t = 1;scanf("%lld %lld %lld",&a,&b,&m);while(b != 0){//b&1：用来判断当前b的二进制最低位是否为1//若为1，则累乘if(b & 1) t = (t * a) % m;//否则，只是将a自乘，并不与最终结果t累乘a = (a * a) % m;//将b向右按位位移1位b >>= 1;}printf("%lld",t);return 0;}操作数
另一种获得位数的巧妙方法
即 位数n=(int)log10(x) + 1
#include//获得各个位数之和long long wsum(long long x){long long h = 0;while(x!=0){h = h + (x % 10);x = x / 10;}return h;}int main(){long long n,i=0;scanf("%lld",&n);while(n>0){n = n - wsum(n);i++;}printf("%lld",i);return 0;}俄罗斯农夫乘法
#includeint main(){long long m,n,sum = 0;scanf("%lld %lld",&m,&n);while(m != 0){printf("%lld %lld\n",m,n);if((m%2) != 0) sum = sum + n;n = n * 2;m = m / 2;}printf("%lld",sum);return 0;}余数和
#includeint main(){int n,k,sum = 0;scanf("%d %d",&n,&k);while(n != 0){sum = sum + k % n;n--;}printf("%d",sum);return 0;}方案数
我们先进行数学上的运算(x = 1,2,3,...)
两个连续正整数的和：x x+1 = 2x+1
三个连续正整数的和：x x+1 x+2 = 3x+3
四个连续正整数的和：x x+1 x+2 x+3= 4x+6
......
i个连续正整数的和：x x+1 ... x+i-2 x+i-1 =i*x+i*(i-1)/2
不难发现当(n-(i*(i-1))/2)%i == 0时，方案成立，则方案数c加1
另外需要注意的是，while循环需要停止条件t=n时，n-t<=0,x不存在
#includeint main(){int n,i = 1,c = 0,t;scanf("%d",&n);do{if((n-(i*(i-1))/2)%i == 0) c++;i++;t = (i*(i-1))/2;}while(t<n);printf("%d",c);return 0;}竖式乘法
#include//获得位数（考虑x可能为0的情况）int ws(int x){int n=0;if(x != 0){while(x>0){x /= 10;n++;}}else n = 1;return n;}int main(){int a,b,t,tb,wb,c,ca,cb=0;scanf("%d %d",&a,&b);int m[b+1];tb = b;t = a * b;//获得最终结果位数c = ws(t) + 1;//获得a的位数ca = ws(a);//获得b的位数及每一位数while(tb>0){wb = tb % 10;tb /= 10;++cb;m[cb] = wb;}//输出前三行for(int i = 1;i <= c - ca;i++) printf(" ");printf("%d\n",a);printf("x");for(int i = 2;i <= c - cb;i++) printf(" ");printf("%d\n",b);for(int i = 1;i <= c;i++) printf("-");printf("\n");//输出运算过程for(int i = 1;i <= cb;i++){int tr,wr;tr = a * m[i];wr = ws(tr);if(i != cb){for(int j = 1;j <= (c - wr - i + 1);j++) printf(" ");printf("%d",tr);for(int j = 1;j <= i - 1;j++) printf(" ");printf("\n");}else{printf("+%d",tr);for(int j = 1;j <= i - 1;j++) printf(" ");printf("\n");}}for(int i = 1;i <= c;i++) printf("-");//输出最终结果printf("\n %d",t);return 0;}好数字
数学上的排列组合
0~9中偶数有0，2，4，6，8共五个，素数有1，3，5，7共四个
同时为了避免累乘过程超出数据范围，我们每次乘4或5时都同时%mod
另：
使用mod进行取模的原因防止计算时出现溢出，相加时防止int类型溢出，相乘防止long类型溢出
同时当数值比mod小的时候，取余数，对结果不会有影响。
#includeint main(){long long n,r=1,mod=1e9+7;scanf("%lld",&n);for(long long i=1;i<=n;++i){if(i%2 != 0) r = (r * 5) % mod;else r = (r * 4) % mod;}printf("%lld",r);return 0;}查找数列
为了减少循环次数，我们从a = sqrt(n)开始
因为：
√n*(√n+1)/2 = (n+√n）/ 2 < n
#include#includeint main(){double n;long long a;scanf("%lf",&n);a = sqrt(n);while(((a+1)*(a+2)/2)<n) a++;printf("%g",n-a*(a+1)/2);return 0;}最大数字
#includeint main(){unsigned int n;scanf("%u",&n);for(unsigned int i=n;i>0;--i){//设置一个标志变量cunsigned int t=i,a,b,c=1;while(t>9){a = t % 10;t /= 10;b = t % 10;if(b < a) c = 1;else c = 0;}if(c){printf("%u",i);break;}}return 0;}阶乘倍数
找到正确写法啦
终于不超时了！！！
梳理一下思路：
首先如果我们用嵌套for循环来遍历，直到找到符合的n的方法，会发现系统判断超时。我们需要对代码做进一步优化，降低时间复杂度。
一、
对于任一正整数来说，如果从1到sqrt(k)都没有它的因数，则该正整数在1到n上一定没有因数。
这并不难理解，我们以36举例：
1×36=36 2×18=36 3×12=36 4×9=36 6×6=36
简单来说就是，如果 i 为正整数k在1到sqrt(k)上的一个因数，那么n / i 也一定是n的一个因数。
二、
我们仔细思考一下题目的问题会发现，其实求一个最小的a满足a!是给定k的倍数，就是在找，1到n中k的所有因数里，最少相乘到哪个因数的最终结果等于k。
因为如果a！是k的倍数，那么k一定能拆解为1到a中k的因数的乘积的形式。
三、
接下来就需要找到这个最小的a了
我们采取的算法是，for循环从1遍历到sqrt(k)，如果发现 i 是k的因数(即k%i==0)，就将k/i，同时暂存这个目前最大的因数，如此循环，直到k被彻底拆解(即k==1)，利用break语句跳出循环。
四、
那么如果在1到sqrt(k)内k没有被彻底拆解该怎么办呢？
我们只需要找到第一个大于当前最大因数y且为当前k的整数倍的数就可以了
（贴个图方便理解）
#include#includeint main(){long long k,s,y=1,a=1,c=1;scanf("%lld",&k);s = sqrt(k);for(long long i=2;i<=s;++i){if(k%i==0){k /= i;y = i;}if(k==1){printf("%lld",i);return 0;}}do{a=k*c;c++;}while(a<=y);printf("%lld",a);return 0;}倒水
分两种情况
一、先倒满小杯
二、先倒满大杯
我们参照题目给出例子写出详细过程后，仔细思考发现，下一步的最优操作是由本步两杯水的情况决定的，因此我们分别考虑不同的情况（存在规律），并给出下一步的运算方式
#includeint firtype(int m,int n,int d){int a=m,b=0,i=1;while(1){if(a!=0&&b==0){b=a;a=0;i++;if(a==d||b==d) break;}if(a==0&&b!=0){a=m;i++;if(a==d||b==d) break;}if(a==m&&b!=0){b=b+a;if(b>n){a=b-n;b=n;}else a=0;i++;if(a==d||b==d) break;}if(a!=0&&b==n){b=0;i++;if(a==d||b==d) break;}}return i;}int sectype(int m,int n,int d){int a=0,b=n,i=1;while(1){if(b==n){b=b-(m-a);a=m;i++;if(a==d||b==d) break;}if(a==m&&b!=0){a=0;i++;if(a==d||b==d) break;}if(a==0&&b!=0){a=b;b=0;i++;if(a==d||b==d) break;}if(a!=0&&b==0){b=n;i++;if(a==d||b==d) break;}}return i;}int mini(int a,int b){return a毕达哥拉斯三元组
说在前面：
调试了好久，最后发现时数据类型定义小了，把long long换成unsighed long long就顺利AC了
思路：
主要是条件的预处理：
1.c的大致范围
由a+b+c=n，a<b(a+b)/2,即c>(n-c)/2,解得c>n/3
由c^2=a^2+b^2<(a+b)^2,我们可以得到c
2.a的大致范围
由a<b,a^2+b^2=c^2,我们可以得到a^2<b^2,即a^2<c^2-a^2，解得a<c/√2
由a<b,a+b+c=n,我们可以得到a<n-c-a,解得a<(n-c)/2
取min{c/√2 , (n-c)/2}
#include#includeint mini(int x,int y){return xn/3;c--){int t = mini((int)(c/sqrt(2)),(n-c)/2);for(unsigned long long a=1;a<=t+1;a++){unsigned long long b=n-c-a;if((a*a+b*b)==c*c){r = a*b*c;printf("%llu\n",r);break;}}}return 0;}不知道具体什么原因，上面这个方法目前（10月12以后）无法AC了
下面这个代码目前可AC
#includeint main(){int n;scanf("%d",&n);for(int c=n/2;c>n/3;--c){for(int a=1;a<n-c;++a){int b=n-c-a;if(a*a+b*b==c*c){printf("%d",a*b*c);return 0;}}}}可变参数累加
函数讲解可参考这篇文章：va_start和va_end详解
#include#includeint sum(int n,...){va_list ap;va_start(ap,n);int r = 0;for(int i=1;i<n;++i){r = r + va_arg(ap,int);}va_end(ap);return r;}int main(){int a,b,c,d,e,f;int ans;scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f);ans = sum(3,a,b,0)-sum(5,c,d,e,f,0);printf("%d",ans);return 0;}基斯数
暂时不太会用内联函数，所以我选择了先不用 orz
#include#includelong sum(long a[],long c,long ans){int r=0;for(int i=0;i=0;--i){a[i]=bn%10;bn /= 10;}do{ans = sum(a,c,ans);if(ans==n){printf("Yes");return 0;}for(int i=0;i<c-1;++i){a[i]=a[i+1];}a[c-1]=ans;}while(ans<=n);printf("No");return 0;}运动会
思路：
能看见的条件为：班长和能看见的同学所连成的直线上没有其他的同学
以班长为（0，0），向右为x轴，向上为y轴正方向建立平面直角坐标系，则每位同学的位置可以用坐标（x，y）表示，班长能看见的同学人数，就等于与原点连线斜率第一次出现的次数
而斜率k可以表示为
，斜率k的最简形式为化简至分子与分母互质
问题再一次转化为在0< x,y <=n时，由x，y组成的互质坐标对数
由于是n×n的队伍，我们y=x直线两侧三角形区域中的一个就可以了，若这部分求得的互质坐标对数为r，则最终结果为2*r+1（加的1为k=1）
解决过程：
欲求出互质坐标对数，我们可以通过for循环遍历来进行，但这样会超时，于是学到了一个新的算法，即欧拉函数（用于求不超过x的与x互质的数的个数）
学习了这些文章：欧拉函数(Euler_Function)、欧拉函数（详解）-数论、欧拉函数(详细证明+推导) 每日一遍，算法再见！
先需要了解数学上关于欧拉函数的证明，可自行网上搜索学习，这里贴一下好朋友教我的简化版证明：
为什么编写Euler函数for循环截止到sqrt(n)，原因在之前的题目中已经解释，这里省略
同时我们引入一个新的定理：算术基本定理
可表述为：任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积
那么对n来说，从i=2开始，如果n能被i整除，我把n中的因子i都除掉后，n能被整除的下一个i一定是原n的质因数，这就是程序里面while的意义。
#include#include//Eratosthenes筛法求欧拉函数int Euler(int n){long longans=n;for(int i=2;i1) ans=ans/n*(n-1);return ans;}int main(){long longn,r=0;scanf("%lld",&n);for(int i=1;i<n;++i){r = r + Euler(i);}printf("%lld",2*r+1);return 0;}可变参数平均
#include#includedouble avg(int n,...){double sum = 0;va_list ap;va_start(ap,n);for(int i=1;i<=n;++i){sum = sum + va_arg(ap,double);}va_end(ap);return sum/n;}int main(){double a,b,c,d,e,ans;scanf("%lf %lf %lf %lf %lf",&a,&b,&c,&d,&e);ans = avg(2,a,b) - avg(3,c,d,e);printf("%.4lf",ans);return 0;}佩尔数
#includeint PA(int n){//递归方法if(n==0) return 0;if(n==1) return 1;return 2*PA(n-1) + PA(n-2);}int PB(int n){//递推方法int p0 = 0,p1 = 1,pn;if(n==0) pn = p0;else if(n==1) pn = p1;else{for(int i=2;i<n+1;++i){pn = 2*p1 + p0;p0 = p1;p1 = pn;}}return pn;}int main(){int n;scanf("%d",&n);if(n%2==0) printf("%d",PB(n));else printf("%d",PA(n));return 0;}素数
for循环全部遍历会超时
算法优化思路：
所有大于5的素数均与6的倍数相邻
证明即思路来自这篇文章：判断一个数是否为质数（素数）的4种方法
#include#include//判断一个数是不是素数int PrimeNum(int x){for(int i=3;i<=sqrt(x);i+=2){if(x%2==0||x%i==0) return 0;}return 1;}int main(){int m,n,t,c = 0,a,b;scanf("%d %d",&m,&n);if(n==2){printf("1");return 0;}if(n==3){printf("2");return 0;}if(n==4){if(m==1){printf("2");}else printf("1");return 0;}t = m/6;while(6*t+1<m) t++;while(6*t-1=m&&PrimeNum(a)) c++;if(b<=n&&PrimeNum(b)) c++;t++;}printf("%d",c);return 0;}光线追踪
此题为洛谷原题，深入学习了洛谷大犇的写法，太太太强了！！！
提示：思考反射过程与更相减损术的联系，考虑更相减损术的几何表示
把原文放在这里：AT_agc001_b [AGC001B] Mysterious Light 题解
#includelong long gcd(long long x,long long y){return y==0?x:gcd(y,x%y);}int main(){long long a,n;scanf("%lld %lld",&a,&n);printf("%lld",3*(a-gcd(a,n)));return 0;}二进制表示
想到应该要用递归，但是暂时没成功码出代码，再磨几天qwq。
看了看另一位同学的想法，思路清晰啊 orz
终于码出来了，逆向相加至所给数比正向分解所给数要简单不少
#include//无返回值函数的递归使用void BinaryPrest(int x){if(x == 0){printf("0");return;}if(x == 1){printf("2(0)");return;}if(x == 2){printf("2");return;}int c = 0;while((1 << (c + 1)) <= x){c++;}if(c == 1){printf("2");}else{printf("2(");BinaryPrest(c);printf(")");}// << 左移运算if((x - (1 << c)) != 0){printf("+");BinaryPrest(x - (1 << c));}}int main(){int n;scanf("%d",&n);BinaryPrest(n);return 0;}冰雹序列
#includeint main(){int n;scanf("%d",&n);printf("%d",n);while(n!=1){if(n%2!=0){n = 3 * n + 1;printf(" %d",n);}else{n = n / 2;printf(" %d",n);}}return 0;}哈沙德数
#includeint HarshadNumber(int n){int s=0,x=n;while(x!=0){s = s + x % 10;x /= 10;}if(s==0||n%s!=0||n==1) return 0;else return n/s;}int main(){int n,c=0;scanf("%d",&n);while(HarshadNumber(n)!=0){n = HarshadNumber(n);c++;}printf("%d",c);return 0;}11月27日更新：
拖更了好久，事情太多，并且数组和字符串需要学习的新知识太多，边学边写，效率降低好多，先把AC代码贴出来，注释后续慢慢补上orz
(目前飞机起飞速度和字符串替换还未AC，据说是noj平台的问题）
回文数之和
#include#includeint Answer(int n,int k){int a[99],b[99],c=0,d=0,x=n,t=1;do{a[c++] = x%k;x /= k;}while(x!=0);do{b[d++] = n%10;n /= 10;}while(n!=0);for(int i=0;i<d/2;++i){if(b[i] != b[d-i-1]){t=0;break;}}for(int i=0;i0;--i){if(Answer(i,k)) result+=i;}printf("%d",result);return 0;}蒙特卡洛方法求积分
想AC注意一点即可，去样本量进行计算时记得少取一个（但样本总量仍不变），如：样例2000个样本，求积分时循环取够1999个即可，这是题目本身的问题，知道就好。
知识积累：
1. C 标准库函数double exp(double x)返回e的x次幂的值。
2. 随机数相关知识可阅读以下文章：
RAND_MAX的使用及rand（）函数使用、C语言随机函数：rand（）和srand()的使用及示例
#include#include#includedouble Function1(double a,double b,int N,double c[]){double ans=0;for(int i=0;i<N-1;++i){ans += c[i]*c[i]*c[i]*c[i]*(b-a)/exp(c[i]);}return ans/N;}double Function2(double a,double b,int N,double c[]){double ans=0;for(int i=0;i<N-1;++i){ans += (c[i]*c[i]+1)*(b-a);}return ans/N;}double Function3(double a,double b,int N,double c[]){double ans=0;for(int i=0;i<N-1;++i){ans += cos(c[i])*(b-a);}return ans/N;}double Function4(double a,double b,int N,double c[]){double ans=0;for(int i=0;i<N-1;++i){ans += sqrt(c[i])*(c[i]-2)*(b-a);}return ans/N;}double Function5(double a,double b,int N,double c[]){double ans=0;for(int i=0;i<N-1;++i){ans += (2*sin(c[i])-5*cos(c[i]))*(b-a);}return ans/N;}int main(){int m,N;double a,b;scanf("%d %lf %lf %d",&m,&a,&b,&N);srand(RAND_MAX);double c[N-1];for(int i=0;i<N-1;++i){c[i] = rand()*1.0/RAND_MAX*(b-a) + a;}switch(m){case 1:{printf("%.6lf",Function1(a,b,N,c));break;}case 2:{printf("%.6lf",Function2(a,b,N,c));break;}case 3:{printf("%.6lf",Function3(a,b,N,c));break;}case 4:{printf("%.6lf",Function4(a,b,N,c));break;}case 5:{printf("%.6lf",Function5(a,b,N,c));break;}}return 0;}素数筛选法
下面展示的代码分别为埃氏筛的改进版与欧拉筛，实际提交测试发现，改进版的埃氏筛比欧拉筛还快上一点点
关于解决素数筛选过程中学习参考的文章如下：
埃氏筛改进版：
#includechar a[10000000]={0};int main(){int n,ans=0;scanf("%d",&n);for(int i=2;i*i<=n;++i){if(a[i]) continue;for(int j=i*i;j<=n;j+=i){a[j]=1;}}for(int i=2;i<=n;++i){if(!a[i]) ans++;}printf("%d",ans);return 0;}欧拉筛：
#includeint a[10000001];int prime[10000001];int main(){int n,ans=0,cnt=0;scanf("%d",&n);for(int i=2;i<=n;++i){if(!a[i]) prime[cnt++]=i;for(int j=0;j<cnt&&prime[j]<=n/i;++j){a[prime[j]*i]=1;if(i%prime[j]==0) break;}}printf("%d",cnt);return 0;}航空旅行
#include #include void CanorNot(int a[][5],int n){for(int i=0;i<n;++i){int t=0,sum=0;int m=a[i][3],n=a[i][4];for(int j=0;j<3;++j){if(a[i][j]=t) t=a[i][j];sum += a[i][j];}if(t==0) printf("NO\n");else if((sum-t)<=m) printf("YES\n");else printf("NO\n");}}int main(){int n;scanf("%d",&n);int a[36000][5];for(int i=0;i<n;++i)for(int j=0;j<5;++j)scanf("%d",&a[i][j]);CanorNot(a,n);return 0;}稀疏矩阵
#include#includeint main(){int m,n,sum=0,cnt=0;int a[10000];scanf("%d %d",&m,&n);for(int i=0;i<m*n;++i)scanf("%d",&a[i]);for(int i=0;i<m*n;++i){if(a[i]!=0) cnt++;sum += a[i];}if(cnt*20<=sum||(cnt==m||cnt==n)) printf("Yes");else printf("No");return 0;}飞机起飞速度
暂无
完美矩阵
#include #include int n,m;int Mini(int p,int q){return p1;--k){int cnt1=0,cnt2=0,t=1;for(int i=x;i<x+k;++i){for(int j=y;j-2&&cnt2<2) cnt++;}}return cnt;}int main(){int sum=0;int a[300][300];scanf("%d %d",&n,&m);for(int i=0;i<n;++i)for(int j=0;j<m;++j)scanf("%d",&a[i][j]);for(int i=0;i<n-1;++i){ for(int j=0;j<m-1;++j){if(!a[i][j]) continue;else sum += Judge(i,j,a);}}printf("%d",sum);return 0;}
行列式值
#include#includeint Cauclt_Det(int a[20][20],int n);int Cofactor(int a[20][20],int i,int n);int Cauclt_Det(int a[20][20],int n){int sum=0,c;if(n==1) return a[0][0];else{for(int i=0;i<n;++i){c = Cofactor(a,i,n);sum += pow(-1,i+2) * a[0][i] * c;}}return sum;}int Cofactor(int a[20][20],int i,int n){int b[20][20];for(int j=0;j<n-1;++j){for(int k=0;k<n-1;++k){if(k<i) b[j][k] = a[j+1][k];else b[j][k] = a[j+1][k+1];}}return Cauclt_Det(b,n-1);}int main(){int n,a[20][20];scanf("%d",&n);for(int i=0;i<n;++i)for(int j=0;j<n;++j)scanf("%d",&a[i][j]);printf("%d",Cauclt_Det(a,n));return 0;}货运优化
此为annesde的源代码，自己之前写的找不到了......
#include int main() {int l3s2[4] = {0, 5, 3, 1};int n, x1, x2, x3, x4, x5, x6, s2, s1;while (1) {scanf("%d %d %d %d %d %d", &x1, &x2, &x3, &x4, &x5, &x6);if ((x1 + x2 + x3 + x4 + x5 + x6) == 0) break;n = (x3 + 3) / 4 + x4 + x5 + x6;s2 = 5 * x4 + l3s2[x3 % 4];if (x2 > s2) n += (x2 - s2 + 8) / 9;s1 = 36 * n - 36 * x6 - 25 * x5 - 16 * x4 - 9 * x3 - 4 * x2;if (x1 > s1) n += (x1 - s1 + 35) / 36;printf("%d\n",n);}return 0;}波士顿房价预测
#includeint main(){int n;double a,b,xy=0,avrg_x=0,avrg_y=0,sqr_x=0;scanf("%d",&n);double q[n][2];for(int i=0;i<n;++i)scanf("%lf%lf",&q[i][0],&q[i][1]);for(int i=0;i<n;++i){xy += q[i][0]*q[i][1];avrg_x += q[i][0];avrg_y += q[i][1];sqr_x += q[i][0]*q[i][0];}b = (xy - (avrg_x*avrg_y/n)) / (sqr_x - avrg_x*avrg_x/n);a = avrg_y/n - b*avrg_x/n;printf("Y=%.4lf+%.4lf*X",a,b);return 0;}删除前后缀
#include#includechar *str_removeprefix(char *str,char *dstr);char *str_removesuffix(char *str,char *dstr);void Reverse_order(char *rsfs);void Reverse_order(char *rsfs){char brsfs[100000];strcpy(brsfs,rsfs);int x=strlen(rsfs);for(int i=0;i<x;++i){(*(rsfs+i)) = brsfs[x-i-1];}}char *str_removeprefix(char *str,char *dstr){int len1,len2;static char *rpfs=str;len1=strlen(str);len2=strlen(dstr);int c=len1/len2;for(int i=0;i<c;++i){int t=1;for(int j=0;j<len2;++j){if(*(rpfs+j)!=*(dstr+j)){t=0;break;}}if(t==1) rpfs += len2;else break;}return rpfs;}char *str_removesuffix(char *str,char *dstr){int len1,len2;static char *rsfs=str;len1=strlen(str);len2=strlen(dstr);int c=len1/len2;Reverse_order(rsfs);Reverse_order(dstr);for(int i=0;i<c;++i){int t=1;for(int j=0;j<len2;++j){if(*(rsfs+j)!=*(dstr+j)){t=0;break;}}if(t==1) rsfs += len2;else break;}Reverse_order(rsfs);return rsfs;}int main(){int c,p=0,d,q=0;char str[100000]="",dstr[100000]="";scanf("%[^\n] %[^\n]",str,dstr);printf("%s\n",str_removeprefix(str,dstr));printf("%s",str_removesuffix(str,dstr));return 0;}Atol转换
#include#includeint main(){char str[1000]="",ans[1000]="",j=0,cnt=0,t=0;char min[]="2147483648",max[]="2147483647";scanf("%[^\n]",str);int len=strlen(str);for(int i=0;i='0'&&str[i]<='9'){ans[j++]=str[i];cnt++;t=1;continue;}else break;}ans[j]='\0';char *p=ans;if(cnt!=0){while(*p=='0'||*p=='+') p++;if(*p=='-'){if(strlen(p+1)strlen(min)) printf("-2147483648");else{if(strcmp((p+1),min)>0) printf("-2147483648");else printf("%s",p);}}else{if(strlen(p)strlen(max)) printf("2147483647");else{if(strcmp(p,max)>0) printf("2147483647");else printf("%s",p);}}}else printf("0");return 0;}大小写交换
#include#includevoid str_swapcase(char *p){int len=strlen(p);for(int i=0;i='a'&&*p='A'&&*p<='Z') *p = *p+32;}p++;}}int main(){char str[1000]="";scanf("%[^\n]",str);str_swapcase(str);printf("%s",str);return 0;}前后缀移除
#include#includeint str_lstrip(char str[],char dstr[],int len1,int len2){int i=0;for(;i<len1;++i){int j=0,t=0;for(;j-1;--i){int j=0,t=0;for(;j<len2;++j){if(str[i]==dstr[j]){t=1;break;}}if(t==0) break;}return i;}int main(){char str[100000]="",dstr[100000]="";int a,b;scanf("%[^\n] %[^\n]",str,dstr);int len1=strlen(str),len2=strlen(dstr);a=str_lstrip(str,dstr,len1,len2);b=str_rstrip(str,dstr,len1,len2);for(int i=a;i<len1;++i)printf("%c",str[i]);printf("\n");for(int i=0;i<=b;++i)printf("%c",str[i]);printf("\n");for(int i=a;i<=b;++i)printf("%c",str[i]);return 0;}字符串替换
暂无
分离字符串
#include#includeint str_find(char *str,char sep[],int len1,int len2){int i=0,j=0,m;for(;i<len1;++i){if(*(str+i) == sep[0]){m=i;int t=1;for(int j=1;j<len2;++j){if(*(str+i+j)!=sep[j]){t=0;break;}}if(t==0) continue;else return m;}}return -1;}void str_split(char nstr[],char *p,char sep[]){int x=strlen(p);int y=strlen(sep);int c=x/y;int j=0;for(int i=0;i<c;++i){int cnt=str_find(p,sep,x,y);if(cnt!=-1){for(int k=0;k<cnt;++k){printf("%c",*(p+k));}p += (cnt+y);printf("\n");}else{printf("%s",p);return;} }}int main(){char str[2000]="",sep[20]="",nstr[2000]="";scanf("%[^\n]",str);getchar();scanf("%[^\n]",sep);str_split(nstr,str,sep);return 0;}元宇宙A+B
第一个是我自己写的，测试数据都正确，但noj无法AC（如果有大佬发现漏洞，请务必告知，跪谢orz）
第二个是annesede的源代码（可AC），太厉害了，学习学习学习！
#include#includeint CtoI(char x){switch(x){case '0': return 0;case '1': return 1;case '2': return 2;case '3': return 3;case '4': return 4;case '5': return 5;case '6': return 6;case '7': return 7;case '8': return 8;case '9': return 9;case 'A': return 10;case 'B': return 11;case 'C': return 12;case 'D': return 13;case 'E': return 14;case 'F': return 15; case 'G': return 16; case 'H': return 17; case 'I': return 18; case 'J': return 19; case 'K': return 20; case 'L': return 21; case 'M': return 22; case 'N': return 23; case 'O': return 24; case 'P': return 25; case 'Q': return 26; case 'R': return 27; case 'S': return 28; case 'T': return 29; case 'U': return 30; case 'V': return 31; case 'W': return 32; case 'X': return 33; case 'Y': return 34; case 'Z': return 35; }}char ItoC(int y){switch(y){case 0: return '0';case 1: return '1';case 2: return '2';case 3: return '3';case 4: return '4';case 5: return '5';case 6: return '6';case 7: return '7';case 8: return '8';case 9: return '9';case 10: return 'A';case 11: return 'B';case 12: return 'C';case 13: return 'D';case 14: return 'E';case 15: return 'F';case 16: return 'G';case 17: return 'H';case 18: return 'I';case 19: return 'G';case 20: return 'K';case 21: return 'L';case 22: return 'M';case 23: return 'N';case 24: return 'O';case 25: return 'P';case 26: return 'Q';case 27: return 'R';case 28: return 'S';case 29: return 'T';case 30: return 'U';case 31: return 'V';case 32: return 'W';case 33: return 'X';case 34: return 'Y';case 35: return 'Z';}}int main(){char a[100]="",b[100]="",e[101]="";int c[100]={0},d[100]={0},f[101]={0};scanf("%s %s",a,b);int len1=strlen(a);int len2=strlen(b);int max=len1>len2?len1:len2;for(int i=len1-1;i>-1;--i){c[len1-i-1]=CtoI(a[i]);}for(int i=len2-1;i>-1;--i){d[len2-i-1]=CtoI(b[i]);}int j=0;for(int i=0;i<max;++i){int t=c[i]+d[i];if(t-1;--i){printf("%c",ItoC(f[i]));}return 0;}#include #include const static char decToMeta[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";static char c[100] = "", a[100] = "", b[100] = "";static int C[100] = {0}, A[100] = {0}, B[100] = {0}; int metaToDec(char m) {if ('0' <= m && m <= '9') return m - '0';return m - 'A' + 10;} void add(void) {int lenA = strlen(a), lenB = strlen(b);for (int i = 0; i < lenA; ++i) A[i] = metaToDec(a[lenA - i - 1]);for (int i = 0; i lenB ? lenA : lenB;for (int i = 0; i = 0; --i) c[i] = decToMeta[C[lenC - i - 1]];c[lenC] = '\0';} int main() {scanf("%s %s", a, b);add();puts(c);return 0;}Kids A+B
#include#includechar eg[][10]={"zero","one","two","three","four","five",\"six","seven","eight","nine","ten","eleven","twelve","thirteen",\"fourteen","fifteen","sixteen","seventeen","eighteen","nineteen",\"twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"};int num[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,\30,40,50,60,70,80,90};int CtoI(char x[]){for(int i=0;i<29;++i){if(strstr(eg[i],x)!=NULL){if(i<20) return i;else return ((i%10)+2)*10;}}}int ItoC(int x){for(int i=0;i<29;++i){if(num[i]==x) return i;}}void str_split(char *p,char x[],char y[]){char *l=strstr(p,"-");if(l!=NULL){strncpy(x,p,l-p);strcpy(y,(l+1));}else{strcpy(y,p);}}int main(){char a[15]="",b[15]="";char c[10]="",d[10]="",e[10]="",f[10]="";int m,n,p,q;scanf("%s %s",a,b);str_split(a,c,d);str_split(b,e,f);m=CtoI(c);n=CtoI(d);p=CtoI(e);q=CtoI(f);int h1,h2;h1=m+p;h2=n+q;if(h1+h2<21||(h1+h2)%10==0){printf("%s",eg[ItoC(h1+h2)]);}else{if(h2<10){printf("%s-%s",eg[ItoC(h1)],eg[ItoC(h2)]);}else{int t=h2/10*10;printf("%s-%s",eg[ItoC(h1+t)],eg[ItoC(h2-t)]);}}return 0;}字符串后缀
#include#includeint main(){char str[100]="",sfx[100]="";scanf("%[^\n]",str);getchar();scanf("%[^\n]",sfx);int len1=strlen(str);int len2=strlen(sfx);int t=1,j=len2-1;for(int i=len1-1;i>-1;--i){if(str[i]==sfx[j--]) break;else{t=0;break;}if(t==0) break;}if(t==1) printf("Yes");else printf("No");return 0;}字符串切片
#include#include#includevoid Tosame(int slc[],int len){for(int i=0;i<2;++i){if(slc[i]<0) slc[i] += len;}}void str_slice(char str[],int slc[],char ans[][1000],int j){int k=0;if(slc[2]slc[1];i+=slc[2])ans[j][k++]=str[i];}else{for(int i=slc[0];i<slc[1];i+=slc[2])ans[j][k++]=str[i];}}int main(){char str[1000]="";int t;scanf("%[^\n]",str);int len=strlen(str);scanf("%d\n",&t);char ans[t][1000]={""};for(int i=0;i<t;++i){int n,slc[3];scanf("%d",&n);if(n==1){slc[1]=len;slc[2]=1;}if(n==2) slc[2]=1;for(int j=0;j<n;++j){scanf(" %d",&slc[j]);}Tosame(slc,len);str_slice(str,slc,ans,i);}for(int i=0;i<t;++i) printf("%s\n",ans[i]);return 0;}