a和b的LCM是n，GCD是m，那么n=a/m*b ， 它们的和就是sum=a+b; 如果m不为1（即a和b不互质），那么我们为什么不优化一下，将a变为a=a/m呢？，改变后a和b的LCM依然是n，但是他们的和显然减少了 所以我们得到最重要的一个性质，要想a1，a2，a3……an的和最小，要保证他们两两互质，只要存在不互质的两个数，就一定可以近一步优化 那我们怎么保证两两互质呢？方法其实很简单，直接分解质因子 例如264600=8*27*25*49  ， 只是由3个2,3个3,2个5,2个7，处理后得到的因子，那么8,27，25,49的LCM是...

c++用的是Windows，g++用的是Linux 重大不同就是有些编译器对此十分严格，如UVA等； 在c++中 long long 的输入输出是 "%lld" 在g++中 long long 的输入输出是 "%I64d" 在uva10791中因为这个小问题卡了贼久

工具——编译选项——编译时添加以下命令 -std=c++11 加后可以用 for(auto it:ans){ } vector<int> a; auto ans=a;

n的质因数最多一个大于根号n 反证法：假设有两个，则两者相乘大于n #include <bits/stdc++.h> using namespace std; int t,n; void divide(){ for(int i=2;i<=n/i;i++){  if(n%i==0){ int num=0; while(n%i==0){ n/=i;// 防止出现被合数除  num++; } printf("%d...

筛质数一般有两种方法：埃氏筛法、线性筛法，一般用线性筛法，更快 埃氏筛法：把所有质数的倍数筛掉 线性筛法：让所有合数被他的最小质因数筛掉 如3*7=21， 埃氏筛法21被3和7分别操作一次 线性筛法21只被3操作一次 埃氏筛法：（洛谷IDE） 时间复杂度n*ln（n） 查找1~1e7约200ms，内存11mb 查找1~1e8（>2000s）报超时 线性筛法：（洛谷IDE） 查找1~1e7约160ms ，内存12mb； 查找1~1e8约1210ms，内存121mb #include <bits/stdc...

#include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> using namespace std; const int N=14; int n,m,num[6]; int a[N][N]; char c; int flag; int dirx[4]={0,1,0,-1}, diry[4]={1,0,-1,0}; int vis[N][N]; struct Node{ int x...

所有权值为一的点求最短路一般用bfs；权值不同的点求最短路用优先队列：poj2312其他用dfs二维限制用dfs+剪枝，如路程时间+路程费用求费用内最短时间用dfs：poj1724求数组里面选满足条件数字可用dfs：hdu1015ps：用dfs时要注意dfs函数里一些变量不要用全局，全局会保留数值使得变量不会自动刷新