111 / 423 Problem A LightOJ 1370 Bi-shoe and Phi-shoe
d.给出n个数a1,a2,...,an，对每个数ai分别找到一个相应的数pi，使其欧拉函数值Φ(pi)>=ai，求p1+p2+...+pn的最小值。
s.不知道为什么pi要选大于ai的第一个素数。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std; const int MAXN=; bool isPrime[MAXN]; void sieve(int n){
memset(isPrime,true,sizeof(isPrime));
isPrime[]=isPrime[]=false;
int i,j,k;
k=sqrt(n);
for(i=;i<=k;++i){
if(isPrime[i]==true){
for(j=i+i;j<=n;j=j+i){
isPrime[j]=false;
}
}
}
} int main(){ sieve(MAXN-); int T;
int n;
int t;
int i;
int j;
long long sum;
int ca=; scanf("%d",&T); while(T--){
scanf("%d",&n);
sum=;
for(i=;i<n;++i){
scanf("%d",&t);
for(j=t+;j<MAXN;++j){
if(isPrime[j]==true){
break;
}
}
sum+=j;
}
printf("Case %d: %lld Xukha\n",++ca,sum);
} return ;
}
21 / 74 Problem B LightOJ 1356 Prime Independence
题意：
找出一些数字的最大质独立集，就是集合能的所有数互相之间不会出现 a[i]==t*a[j] (t是质数) 的情况。
思路：
首先想最大独立集对于一般图是NP问题，通常只有求二分图最大独立集，然后就是如何把这些数字分为二分图。
能够想到如果一个数字等于另一个数字乘以一个质数，那么这两个数字的质因子分解应该只有这一个质数的差别。也就是只会多一个质数，数字上限只有500000，完全可以看一个数组储存某个数字是否存在，然后对每个数字分解质因子，找到他对于每个质因子能够找到的那个数，存在则加边，然后就把质因子总个数（可重复的）是奇数与偶数的分成两边并且把只有一个质因子差别的连通，然后二分图匹配求最大独立集即可。
即二分图左边为质因子总数为奇数的，右边为质因子总数偶数的。
关于二分图匹配因为数量较大所以用匈牙利会tle，要用Hopcroft-Carp：
c.根据这个思路写了下，用的匈牙利O(VE)，没超时。不过Hopcroft-Carp这个会快1s左右。
/*
//顶点编号从1开始的
用STL中的vector建立邻接表实现匈牙利算法
效率比较高
处理点比较多的效率很高。1500的点都没有问题
*/
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
using namespace std; const int MAXN=+;//这个值要超过两边个数的较大者，因为有linker
int linker[MAXN];
bool used[MAXN];
vector<int>G[MAXN];
int uN;
bool dfs(int u)
{
int sz=G[u].size();
for(int i=; i<sz; i++)
{
if(!used[G[u][i]])
{
used[G[u][i]]=true;
if(linker[G[u][i]]==-||dfs(linker[G[u][i]]))
{
linker[G[u][i]]=u;
return true;
}
}
}
return false;
} int hungary()
{
int u;
int res=;
memset(linker,-,sizeof(linker));
for(u=; u<uN; u++)
{
memset(used,false,sizeof(used));
if(dfs(u)) res++;
}
return res;
} const int MAXN2=+; bool exist[MAXN2];//标记数是否存在
int a[MAXN];//原来的数
int myHash[MAXN2];//离散化 int factors[MAXN2][];//[0]存质因子，[1]存个数
int factCnt;//不同的质因子总个数
int factCnt2;//包含相同的质因子的总个数 void getFactors(int n){
int i,k;
factCnt=;
factCnt2=;
for(i=,k=sqrt(n);i<=k;++i){
if(n%i==){
factors[factCnt][]=i;
factors[factCnt][]=;
++factCnt2;
n=n/i;
while(n%i==){
++factors[factCnt][];
++factCnt2;
n=n/i;
}
++factCnt;
k=sqrt(n);//循环条件不直接写i<=sqrt(n);是因为这样可以避免重复开跟方
}
}
if(n>){
factors[factCnt][]=n;
factors[factCnt][]=;
++factCnt;
++factCnt2;
}
} int main(){
int T;
int N;
int i;
int j;
int tmp;
int ans;
int ca=; scanf("%d",&T); while(T--){
scanf("%d",&N);
uN=N;//左边集合个数
for(i=;i<uN;++i){//记得要清空
G[i].clear();
} memset(exist,false,sizeof(exist));
for(i=;i<N;++i){
scanf("%d",&a[i]);
exist[a[i]]=true;
myHash[a[i]]=i;//离散化，二分图N个点就可以了
} for(i=;i<N;++i){
getFactors(a[i]);//获取质因子
for(j=;j<factCnt;++j){//枚举质因子
tmp=a[i]/factors[j][];
if(exist[tmp]==true){//tmp存在
if(factCnt2&){//第i个数质因数个数为奇数，第i个数作为左边的点插入一条由左指向右的有向边
G[i].push_back(myHash[tmp]);
}
else{
G[myHash[tmp]].push_back(i);
}
}
}
}
ans=hungary();
printf("Case %d: %d\n",++ca,N-ans);
} return ;
}
c2.Hopcroft-Carp，这个比较快，O(squt(n)*E)
/*
//顶点编号从0开始的
二分图匹配（Hopcroft-Karp算法）
复杂度O(squt(n)*E)
邻接表存图，vector实现
vector先初始化，然后加入边
uN为左端的顶点数，使用前赋值（点编号0开始）
*/
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std; const int MAXN=+;
const int INF=0x3f3f3f3f;
vector<int>G[MAXN];
int uN;
int Mx[MAXN],My[MAXN];
int dx[MAXN],dy[MAXN];
int dis;
bool used[MAXN];
bool SearchP(){
queue<int>Q;
dis=INF;
memset(dx,-,sizeof(dx));
memset(dy,-,sizeof(dy));
for(int i=;i<uN;i++)
if(Mx[i]==-){
Q.push(i);
dx[i]=;
}
while(!Q.empty()){
int u=Q.front();
Q.pop();
if(dx[u]>dis)break;
int sz=G[u].size();
for(int i=;i<sz;i++){
int v=G[u][i];
if(dy[v]==-){
dy[v]=dx[u]+;
if(My[v]==-)dis=dy[v];
else{
dx[My[v]]=dy[v]+;
Q.push(My[v]);
}
}
}
}
return dis!=INF;
}
bool DFS(int u){
int sz=G[u].size();
for(int i=;i<sz;i++){
int v=G[u][i];
if(!used[v]&&dy[v]==dx[u]+){
used[v]=true;
if(My[v]!=-&&dy[v]==dis)continue;
if(My[v]==-||DFS(My[v])){
My[v]=u;
Mx[u]=v;
return true;
}
}
}
return false;
}
int MaxMatch(){
int res=;
memset(Mx,-,sizeof(Mx));
memset(My,-,sizeof(My));
while(SearchP()){
memset(used,false,sizeof(used));
for(int i=;i<uN;i++)
if(Mx[i]==-&&DFS(i))
res++;
}
return res;
} const int MAXN2=+; bool exist[MAXN2];//标记数是否存在
int a[MAXN];//原来的数
int myHash[MAXN2];//离散化 int factors[MAXN2][];//[0]存质因子，[1]存个数
int factCnt;//不同的质因子总个数
int factCnt2;//包含相同的质因子的总个数 void getFactors(int n){
int i,k;
factCnt=;
factCnt2=;
for(i=,k=sqrt(n);i<=k;++i){
if(n%i==){
factors[factCnt][]=i;
factors[factCnt][]=;
++factCnt2;
n=n/i;
while(n%i==){
++factors[factCnt][];
++factCnt2;
n=n/i;
}
++factCnt;
k=sqrt(n);//循环条件不直接写i<=sqrt(n);是因为这样可以避免重复开跟方
}
}
if(n>){
factors[factCnt][]=n;
factors[factCnt][]=;
++factCnt;
++factCnt2;
}
} int main(){
int T;
int N;
int i;
int j;
int tmp;
int ans;
int ca=; scanf("%d",&T); while(T--){
scanf("%d",&N);
uN=N;//左边集合个数
for(i=;i<uN;++i){//记得要清空
G[i].clear();
} memset(exist,false,sizeof(exist));
for(i=;i<N;++i){
scanf("%d",&a[i]);
exist[a[i]]=true;
myHash[a[i]]=i;//离散化，二分图N个点就可以了
} for(i=;i<N;++i){
getFactors(a[i]);//获取质因子
for(j=;j<factCnt;++j){//枚举质因子
tmp=a[i]/factors[j][];
if(exist[tmp]==true){//tmp存在
if(factCnt2&){//第i个数质因数个数为奇数，第i个数作为左边的点插入一条由左指向右的有向边
G[i].push_back(myHash[tmp]);
}
else{
G[myHash[tmp]].push_back(i);
}
}
}
}
ans=MaxMatch();
printf("Case %d: %d\n",++ca,N-ans);
} return ;
}
61 / 332 Problem C LightOJ 1341 Aladdin and the Flying Carpet
题意：给个矩形的面积a,和矩形的最小边长b，问有多少种矩形的方案(不能是正方形)
分析：a可以写成x,y，因为不能是正方形，所以设x<y，那么x<sqrt(a),y>sqrt(a)
所以找到所有小于sqrt(a)的因子，看有几个大于等于b的就是方案数
因子可以由数的唯一分解定理，求得
具体 ： 先筛一遍1e6以内的素数，有线性筛，然后分解a,然后dfs找所有的小于sqrt(a)的因子，
由于前12个素数的乘积大于1e12了，所以这部分复杂度，大概是O（2^12）（一般还要略大，不过大不了多少，数组要开大）左右
可以用这个估计(因为是求小于sqrt(a)的，可以除以2，当然这是空间常数）
所以这部分复杂度是O（T*2^12)满的话（4000*4000）大概也就是几百万，这部分可以忽略不计
主要的复杂度在分解素数里，因为1e6里面大概有7w多素数，这部分复杂度（最坏的情况a是大素数），大概是4000*70000，可以卡过，由于不可能都是这种数据
所以还是可以过的
吐槽：然后我看了看网上的代码，都是先求出总的，然后暴力扫b减，结果居然过了，b是sqrt(a)的级别，是百万，4000*1e6,是4e9，TLE
出题人太良心，没有卡这种的QAQ，感觉略坑啊
#include <cstdio>
#include <iostream>
#include <ctime>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=1e6+;
const int INF=0x3f3f3f3f;
int cnt;
bool v[N];
LL prime[];
void getprime(){
for(int i=;i*i<=N-;++i)
if(!v[i])
for(int j=i*i;j<=N-;j+=i)
v[j]=;
for(int i=;i<=N-;++i)
if(!v[i])prime[++cnt]=i;
}
vector<LL>fac[];
int divisors[],tot;
LL k;
void dfs(int pos,LL res){
if(pos==fac[].size()){
divisors[++tot]=res;
return;
}
for(LL i=,now=;i<=fac[][pos];now*=fac[][pos],++i){
if(now*res>=k)break;
dfs(pos+,res*now);
}
}
int main()
{
getprime();
int cas=,T;
scanf("%d",&T);
while(T--){
printf("Case %d: ",++cas);
LL a,b;
scanf("%lld%lld",&a,&b);
k=sqrt(a);
if(k*k!=a)++k;
if(b>=k){
printf("0\n");
continue;
}
LL t=a;
fac[].clear(),fac[].clear();
for(int i=;i<=cnt&&prime[i]*prime[i]<=t;++i){
if(t%prime[i])continue;
int tmp=;
fac[].push_back(prime[i]);
while(t%prime[i]==)++tmp,t/=prime[i];
fac[].push_back(tmp);
}
if(t>){
fac[].push_back(t);
fac[].push_back();
}
tot=;
dfs(,);
int ans=;
for(int i=;i<=tot;++i)
if(divisors[i]>=b)++ans;
printf("%d\n",ans);
}
return ;
}
法2：根据唯一分解定理，先将a唯一分解，则a的所有正约数的个数为num = (1 + a1) * (1 + a2) *...(1 + ai)，这里的ai是素因子的指数，见唯一分解定理，因为题目说了不会存在c==d的情况，因此num要除2，去掉重复情况，然后枚举小于b的a的约数，拿num减掉就可以了
ps：这个除2很刁。如果存在c==d的情况，会给舍掉。正好符合题意不能是正方形。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
int const MAX = 1e6 + ;
int p[MAX];
bool u[MAX];
int num, cnt;
ll a, b, tmp; void get_prime()
{
memset(u, false, sizeof(u));
for(int i = ; i <= sqrt(MAX); i++)
if(!u[i])
for(int j = i * i; j <= MAX; j += i)
u[j] = true;
for(int i = ; i <= MAX; i++)
if(!u[i])
p[cnt ++] = i;
} void cal()
{
for(int i = ; i < cnt && p[i] <= sqrt(tmp); i++)
{
int cc = ;
while(tmp % p[i] == )
{
cc ++;
tmp /= p[i];
}
num *= (cc + ); }
if(tmp > ) //如果tmp不能被整分，说明还有一个素数是它的约数，此时cc=1
num *= ;
} int main()
{
int T;
scanf("%d", &T);
cnt = ;
get_prime();
for(int ca = ; ca <= T; ca++)
{
scanf("%lld %lld", &a, &b);
if(a < b * b)
printf("Case %d: 0\n", ca);
else
{
num = ;
tmp = a;
cal();
num /= ;
for(int i = ; i < b; i++)
if(a % i == )
num --;
printf("Case %d: %d\n", ca, num);
}
}
}
54 / 82 Problem D LightOJ 1336 Sigma Function
题意：定义f(n)为n的约数之和。比如f(6)=1+2+3+6=12。给出n，求[1,n]中f值为偶数的数的个数。
c.这个代码，，很尴尬，看代码吧。
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std; int main(){ int T;
long long n;
int a,b;
int ca=; scanf("%d",&T); while(T--){
scanf("%lld",&n);
a=sqrt(n);
b=sqrt(n/);
printf("Case %d: %lld\n",++ca,n-a-b);
} return ;
}
正规点的做法：看了这个好像明白上面那个了。。。from：http://www.hardbird.net/lightoj-1336-sigma-function/
大意：定义函数σ(x)为x的所有因子的和。问题是，给一个n，问有多少个σ(x)为偶数,x<=n。
![[kuangbin带你飞]专题十四 数论基础](https://image.shishitao.com:8440/aHR0cDovL3d3dy5oYXJkYmlyZC5uZXQvd3AtY29udGVudC91cGxvYWRzLzIwMTUvMDMvYTEucG5n.png?w=700&webp=1 "[kuangbin带你飞]专题十四 数论基础")
思路：可以计算有多少个σ(x)为奇数，用n减去就好了。题目中给出了提示σ(n)可以写成
![[kuangbin带你飞]专题十四 数论基础](https://image.shishitao.com:8440/aHR0cDovL3d3dy5oYXJkYmlyZC5uZXQvd3AtY29udGVudC91cGxvYWRzLzIwMTUvMDMvYTItMzAweDM2LnBuZw%3D%3D.png?w=700&webp=1 "[kuangbin带你飞]专题十四 数论基础")
其中单独的一项，是等比数列求和的公式。如果要求σ(n)为奇数，那公式中的每一项乘数都得是奇数。
对于其中的第i项乘数f(i)=pi^0+pi^1+…+pi^ei.
当pi=2时，f(i)一定是奇数。
当pi!=2时，由于pi是奇数，只有当ei为偶数时，才能保证f(i)为奇数。
所以，当所有的σ(x)为奇数时，x只有两种情况：
1、所有的ei都为偶数，x就一定是平方数。
2、除了素因子2的指数为奇数外，所有的ei都为偶数，x就一定是平方数的2倍。
#include <cstdio>
using namespace std;
typedef long long LL; int main()
{
int T, kase=;
LL n;
scanf("%d", &T);
while(T--)
{
scanf("%lld", &n);
LL ans=;
for(LL i=; i*i<=n; i++)
{
ans++;
if(*i*i<=n)
ans++;
}
printf("Case %d: %lld\n", ++kase, n-ans);
}
return ;
}
解3：
题意：求[1,n]中约数和为偶数的数的个数
思路：根据算术基本定理的约数和公式f(n)=(1+p1+p1^2+...+p1^k1)(1+p2+p2^2+...+p2^k2)...(1+pn+pn^3+...+pn^kn);
其中n=(p1^k1)*(p2^k2)*...*(pn^kn);(分解素因数)
由于奇数*奇数还是奇数，奇数*偶数或者偶数相乘是偶数。而素数除了2都是奇数。
f(n)的奇偶性取决于每个因子的奇偶性，只要出现一个因子是偶数时f(n)为偶数。
对每个因子，1+p+p^2+...+p^k的奇偶性，
p为素数，当p是2时，式子为奇数；
当p不是2时，p是奇数，p^i为奇数，式子总共k+1项，即k+1个奇数的和，k为偶数时式子为奇数。
以此条件反推dfs出所有的f(n)为奇数的n，方法是每次乘以奇素数素数的两倍或者2，得到的n就是f(n)为奇数的n了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<math.h>
#include<cctype> using namespace std; typedef long long ll;
const int maxn=;
const int INF=(<<);
const double EPS=0.0000000001;
const double Pi=acos(-1.0); ll n;
vector<ll> odd;
bool isprime[maxn];
vector<int> prime;
const ll M=; void play_prime()
{
memset(isprime,,sizeof(isprime));
isprime[]=;
for(int i=;i<maxn;i++){
if(!isprime[i]) continue;
for(int j=i*;j<maxn;j+=i){
isprime[j]=;
}
}
for(int i=;i<maxn;i++){
if(isprime[i]) prime.push_back(i);
}
} void dfs(int dep,ll cur)
{
odd.push_back(cur); for(int i=dep;i<prime.size();i++){
ll t=prime[i];
if(t==){
if(cur<=M/) dfs(i,cur*);
else return;
}
else{
if(cur<=M/(t*t)) dfs(i,cur*t*t);
else return;
}
}
} int main()
{
int T;cin>>T;
play_prime();
dfs(,);
sort(odd.begin(),odd.end());
int tag=;
while(T--){
cin>>n;
ll ans=upper_bound(odd.begin(),odd.end(),n)-odd.begin();
printf("Case %d: %lld\n",tag++,n-ans);
}
return ;
}
66 / 181 Problem E LightOJ 1282 Leading and Trailing
后三位直接用快数幂取余可以求出
前三位我们可以将n^k转化成a.bc * 10^m,这样abc就是前三位了，n^k = a.bc * 10^m
即lg(n^k) = lg(a.bc * 10^m)
<==>k * lg(n) = lg(a.bc) + lg(10^m) = lg(a.bc) + m
m为k * lg(n)的整数部分，lg(a.bc)为k * lg(n)的小数部分
x = lg(a.bc) = k * lg(n) - m = k * lg(n) - (int)(k * lg(n))
a.bc = pow(10, x);
abc = a.bc * 100;
这样前三位数abc便可以求出
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<list>
#include<cmath>
#include<vector>
using namespace std;
long long POW(long long a,long long b,long long c){
if(b==)return ;
long long t=POW(a,b>>,c);
t=t*t%c;
if(b&)t=t*a%c;
return t;
}
int main()
{
long long n,k,i,j,t,test=;
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&k);
double m=k*log10(n)-(long long)(k*log10(n));
m=pow(10.0,m);
printf("Case %lld: %lld %03lld\n",test++,(long long)(m*),POW(n,k,));
}
return ;
}
65 / 216 Problem F LightOJ 1259 Goldbach`s Conjecture
题意：给你一个偶数n,让你求它有多少种可能是两个素数相加得到的
思路：将10000000以内的素数打表，在开一个标志函数，要注意内存，用bool类型
/*
筛法求素数
*/
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
using namespace std; const int MAXN=1e7+; bool a[MAXN];
int prime[MAXN/];
int primeCnt;//素数个数
void sieve(int n){//
memset(a,true,sizeof(a));
int i,j,k;
k=sqrt(n);
a[]=false;
for(i=;i<=k;++i)
if(a[i]==true){
for(j=i+i;j<=n;j=j+i)
a[j]=false;
}
primeCnt=;
for(i=;i<=n;++i){
if(a[i]==true){
prime[primeCnt++]=i;
}
}
} int main(){ sieve(MAXN); int T;
int n;
int i;
int k;
int sum;
int ca=; scanf("%d",&T); while(T--){
scanf("%d",&n);
k=n/;
sum=;
for(i=;prime[i]<=k;++i){
if(a[prime[i]]==true&&a[n-prime[i]]==true){
++sum;
}
}
printf("Case %d: %d\n",++ca,sum);
} return ;
}
65 / 110 Problem G LightOJ 1245 Harmonic Number (II)
先求出前sqrt(n)项和：即n/1+n/2+...+n/sqrt(n)
再求出后面所以项之和.后面每一项的值小于sqrt(n),计算值为1到sqrt(n)的项的个数，乘以其项值即可快速得到答案
例如:10/1+10/2+10/3+...+10/10
sqrt(10) = 3
先求出其前三项的和为10/1+10/2+10/3
在求出值为1的项的个数为(10/1-10/2)个，分别是(10/10,10/9,10/8,10/7,10/6),值为2个项的个数（10/2-10/3）分别是（10/5,10/4）,在求出值为3即sqrt(10)的项的个数.
显然，值为sqrt(10)的项计算了2次,减去一次即可得到答案。当n/(int)sqrt(n) == (int)sqrt(n)时，值为sqrt(n)的值会被计算2次。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std; int main()
{
int T,n;
scanf("%d",&T);
long long sum;
for(int i = ; i<=T; i++)
{
scanf("%d",&n);
sum = ;
for(int j = ; j<=sqrt(n); j++)
{
sum += n/j;
}
for(int j = ; j<=sqrt(n); j++)
{
sum += (n/j - n/(j+))*j;
}
if(n/(int)sqrt(n)==(int)sqrt(n))
sum -= n/(int)sqrt(n);
printf("Case %d: %lld\n",i,sum);
}
return ;
}
48 / 172 Problem H LightOJ 1236 Pairs Forming LCM
思路：把n分解成素因数的形式n=p1^c1+p2^c2+...pm^cm
假设已找到一对（a，b）的lcm=n
有a=p1^d1+p2^d2+...pm^dm
b=p1^e1+p2^e2+...pm^em
易知max(di,ei)=ci
先考虑有序数对（a，b），由唯一分解定理知，a的每一个素因数的幂的大小都决定一个独一无二的数。
所以（a，b）的种数就是(di,ei)的种数，即2*(ci+1)-1(因为有序对(c1,c1)重复了一次所以-1)
所以有序对(a,b)的种数ans=(2*c1+1)*(2*c2+1)*(2*c3+1)*...*(2*cm+1)
但是要求求无序对的种数，已知(a,b)(b,a)重复，除了（n，n）只算了一个之外，所以ans = ans/2 +1
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std; typedef long long ll;
const int N = 1e7+;
ll prime[N/];
bool vis[N];
int tot;
void ini()
{
for(ll i=;i<N;i++)
if(!vis[i])
{
prime[tot++]=i;
for(ll j=i*i;j<N;j+=i) vis[j]=;
}
}
int main()
{
ini();
int T;
scanf("%d",&T);
for(int cas=;cas<=T;cas++)
{
ll n;
cin>>n;
ll t=n;
ll ans=;
for(int i=;i<tot&&prime[i]*prime[i]<=n;i++)
{
ll cnt=;
while(t%prime[i]==) cnt++,t/=prime[i];
ans*=(*cnt+);
}
if(t>) ans*=;
ans = ans/ +;
cout<<"Case "<<cas<<": "<<ans<<endl;
}
return ;
}
43 / 73 Problem I LightOJ 1234 Harmonic Number
求1 + 1/2 + 1/3 + 1/4 + 1/ 5 +...+ 1/ n(1 ≤ n ≤ 108)
这题是单调级数部分求和，网上有公式，不过不知道公式也是没关系的，毕竟这个知识点也偏门了点。。。
我用的方法是打表记录1/i (1<=i<=n)，根据题意，n最大为一亿，将一亿个结果记录下来肯定是不可行的，但是可以记录百万级个结果。下面的代码中，我开了一个250万的数组，0到一亿范围内，每40个数记录一个结果，即是分别记录1/40,1/80,1/120,...,1/一亿，这样对于输入的每个n，最多只需执行39次求倒数运算，大大节省了时间。
注意的是，a[0] = 0,只是为了使得当n==1时不用单独判断。
ps：当n很大时,有个近似公式：1+1/2+1/3+1/4+1/5+...+1/n=γ+ln(n)
γ是欧拉常数,γ=0.57721566490153286060651209...
ln(n)是n的自然对数（即以e为底的对数,e=2.71828...）
我用这个公式写了下，好像精度不太够。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath> using namespace std; const int maxn = ;
double a[maxn] = {0.0, 1.0}; int main()
{
int t, n, ca = ;
double s = 1.0;
for(int i = ; i < ; i++)
{
s += (1.0 / i);
if(i % == ) a[i/] = s;
}
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
int x = n / ;
// int y = n % 40;
s = a[x];
for(int i = * x + ; i <= n; i++) s += (1.0 / i);
printf("Case %d: %.10lf\n", ca++, s);
}
return ;
}
38 / 160 Problem J LightOJ 1220 Mysterious Bacteria
题目大意：给你一个整数n(可能为负数),让你求满足a^p=n的最大的p
思路：当n是正数时,直接对n进行素因子分解，在对它的素因子的个数进行gcd,比如12=2^2*3,gcd(2,1)就是最大的p;
当n是负数时,则p的值一定是奇数,因为一个数的偶数次方一定为整数，因此需要将它的素因子个数全都化为奇数。
#include<stdio.h>
#include<string.h>
const int MAXN=;
bool vis[MAXN];
long long prime[MAXN/];
int tot=;
void getPrime()//求素数
{
for(long long i=;i<MAXN;i++)
if(!vis[i])
{
prime[tot++]=i;
for(long long j=i*i;j<MAXN;j+=i) vis[j]=true;
}
}
int a[];//保存素因子
int b[];//保存素因子的个数
int cnt;
void sbreak(long long n){//进行素因子分解
memset(a,,sizeof(a));
memset(b,,sizeof(b));
cnt=;
for(int i=;prime[i]*prime[i]<=n;i++){
if(n%prime[i]==){
a[cnt]=prime[i];
while(n%prime[i]==){
b[cnt]++;
n/=prime[i];
}
cnt++;
}
}
if(n!=){
a[cnt]=n;
b[cnt++]=;
}
} int gcd(int a,int b) //求最大公约数
{
return b?gcd(b,a%b):a;
} int main(){
int T,ans,kase=,flag;
long long n;
getPrime();
scanf("%d",&T);
while(T--){
flag=;//标志，判断n是正数还是负数
scanf("%lld",&n);
if(n<) n=-n,flag=;
sbreak(n);
int t=b[];
if(!flag){//如果n是奇数
if(t%==){
while(t%==) t/=;
}
for(int i=;i<cnt;i++){//将它的素因子的个数化为奇数
if(b[i]%==){
while(b[i]%==) b[i]/=;
}
t=gcd(t,b[i]);
}
}
else for(int i=;i<cnt;i++) t=gcd(t,b[i]);
printf("Case %d: %d\n",++kase,t);
}
return ;
}
46 / 98 Problem K LightOJ 1214 Large Division
d.问a能否被b整除
s.大数
c.借机水下java大数
import java.math.BigInteger;
import java.util.Scanner; public class Main {//类名要用Main
public static void main(String[] args){ int T;
BigInteger a,b;
BigInteger ZERO=new BigInteger("0");
Scanner sc=new Scanner(System.in);
int ca=0; T=sc.nextInt();
while((T--)>0){ a=sc.nextBigInteger();
b=sc.nextBigInteger();
System.out.print("Case ");
System.out.print(++ca);
if(a.remainder(b).compareTo(ZERO)==0){//b可能为负数，不能用mod函数 System.out.println(": divisible");
}
else{//
System.out.println(": not divisible");
} } }
}
c2.大数模板，好臃肿啊！写起来也麻烦！用了下，还wa了好几发，很尴尬。%运算里面的d可能超int，得用long long才行，这种错不好找啊。。
ps：能少用这个就少用，代码太长。
/*
整数大数
int数组实现
*/
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std; #define MAXN 9999//万进制
#define DLEN 4//4位 class BigNum{
private:
int a[];//可以控制大数位数(500*4)
int len;//大数长度
public:
BigNum(){//构造函数
len=;
memset(a,,sizeof(a));
}
BigNum(const int);//将int转化为大数
BigNum(const char *);//将字符串转化为大数
BigNum(const BigNum &);//拷贝构造函数
BigNum &operator=(const BigNum &);//重载赋值运算符，大数之间赋值 BigNum operator+(const BigNum &)const;//大数+大数
BigNum operator-(const BigNum &)const;//大数-大数
BigNum operator*(const BigNum &)const;//大数*大数
BigNum operator/(const int &)const;//大数/int BigNum operator^(const int &)const;//幂运算
int operator%(const int &)const;//取模
bool operator>(const BigNum &)const;//大数与大数比较
bool operator>(const int &)const;//大数与int比较 void print();//输出大数
}; BigNum::BigNum(const int b){//将int转化为大数
int c,d=b;
len=;
memset(a,,sizeof(a));
while(d>MAXN){
//c=d-(d/(MAXN+1))*(MAXN+1);
c=d%(MAXN+);//取出后四位
d=d/(MAXN+);//
a[len++]=c;
}
a[len++]=d;
}
BigNum::BigNum(const char *s){//将字符串转化为大数
int t,k,index,l,i,j;
memset(a,,sizeof(a));
l=strlen(s);
len=l/DLEN;
if(l%DLEN)++len;
index=;
for(i=l-;i>=;i-=DLEN){
t=;
k=i-DLEN+;
if(k<)k=;
for(j=k;j<=i;++j)
t=t*+s[j]-'';
a[index++]=t;
}
}
BigNum::BigNum(const BigNum &T):len(T.len){//拷贝构造函数
int i;
memset(a,,sizeof(a));
for(i=;i<len;++i)
a[i]=T.a[i];
}
BigNum &BigNum::operator=(const BigNum &n){//重载复制运算符，大数之间赋值
int i;
len=n.len;
memset(a,,sizeof(a));
for(i=;i<len;++i)
a[i]=n.a[i];
return *this;
} BigNum BigNum::operator+(const BigNum &T)const{//大数+大数
BigNum t(*this);
int i,big;//位数
big=T.len>len?T.len:len;
for(i=;i<big;++i){
t.a[i]+=T.a[i];
if(t.a[i]>MAXN){
++t.a[i+];
t.a[i]-=MAXN+;
}
}
if(t.a[big]!=)t.len=big+;
else t.len=big;
return t;
}
BigNum BigNum::operator-(const BigNum &T)const{//大数-大数
int i,j,big;
bool flag;
BigNum t1,t2;//t1大的，t2小的
if(*this>T){
t1=*this;
t2=T;
flag=;//前面的大
}
else{
t1=T;
t2=*this;
flag=;//前面的小
}
big=t1.len;
for(i=;i<big;++i){
if(t1.a[i]<t2.a[i]){
j=i+;
while(t1.a[j]==)++j;
--t1.a[j--];
while(j>i)t1.a[j--]+=MAXN;
t1.a[i]+=MAXN+-t2.a[i];
}
else t1.a[i]-=t2.a[i];
}
while(t1.a[t1.len-]==&&t1.len>){
--t1.len;
--big;
}
if(flag)t1.a[big-]=-t1.a[big-];//前面的小，结果为负
return t1;
}
BigNum BigNum::operator*(const BigNum &T)const{//大数*大数
BigNum ret;
int i,j,up;
int temp,temp1;
for(i=;i<len;++i){
up=;
for(j=;j<T.len;++j){
temp=a[i]*T.a[j]+ret.a[i+j]+up;
if(temp>MAXN){
//temp1=temp-temp/(MAXN+1)*(MAXN+1);
temp1=temp%(MAXN+);
up=temp/(MAXN+);
ret.a[i+j]=temp1;
}
else{
up=;
ret.a[i+j]=temp;
}
}
if(up!=)ret.a[i+j]=up;
}
ret.len=i+j;
while(ret.a[ret.len-]==&&ret.len>)--ret.len;
return ret;
}
BigNum BigNum::operator/(const int &b)const{//大数/int
BigNum ret;
int i,down=;
for(i=len-;i>=;--i){
ret.a[i]=(a[i]+down*(MAXN+))/b;
down=a[i]+down*(MAXN+)-ret.a[i]*b;
}
ret.len=len;
while(ret.a[ret.len-]==&&ret.len>)--ret.len;
return ret;
} BigNum BigNum::operator^(const int &n)const{//幂运算
BigNum t,ret();
int i;
if(n<)exit(-);
if(n==)return ;
if(n==)return *this;
int m=n;
while(m>){
t=*this;
for(i=;i<<<=m;i<<=){
t=t*t;
}
m-=i;
ret=ret*t;
if(m==)ret=ret*(*this);
}
return ret;
}
int BigNum::operator%(const int &b)const{//取模
int i;
long long d=;//这个题这里必须用long long，还得。。可能会超限。
for(i=len-;i>=;--i){
d=((d*(MAXN+))%b+a[i])%b;
}
return d;
}
bool BigNum::operator>(const BigNum &T)const{//大数与大数比较
int ln;
if(len>T.len)return true;
else if(len==T.len){
ln=len-;
while(a[ln]==T.a[ln]&&ln>=)--ln;
if(ln>=&&a[ln]>T.a[ln])return true;
else return false;
}
else return false;
}
bool BigNum::operator>(const int &t)const{//大数与int比较
BigNum b(t);
return *this>b;
} void BigNum::print(){//输出大数
int i;
printf("%d",a[len-]);
for(i=len-;i>=;--i){
printf("%.4d",a[i]);//%.4d代表4位，不够前面补0
}
printf("\n");
} int main(){
/*
char str1[]="2",str2[]="22222222222222222222222222222222222222222222";
int c=2;
//scanf("%s%s",str1,str2);
BigNum a,b,t;
a=BigNum(str1);
b=BigNum(str2);
printf("a=");a.print();
printf("b=");b.print();
printf("c=%d\n",c);
printf("\n"); t=a+b;
printf("a+b=");t.print();
t=a-b;
printf("a-b=");t.print();
t=a*b;
printf("a*b=");t.print();
t=a/c;
printf("a/c=");t.print();
printf("\n"); t=a^c;
printf("a^c=");t.print();
t=a%c;
printf("a%%c=");t.print(); a>b?printf("a>b\n"):printf("a<=b\n");
a>c?printf("a>c\n"):printf("a<=c\n");
*/
int T;
BigNum a;
int b;
char str1[];
int t;
int ca=; scanf("%d",&T); while(T--){
scanf("%s%d",str1,&b);
if(str1[]=='-'){
a=BigNum(str1+);
}
else{
a=BigNum(str1);
}
if(b<){
b=-b;
} t=a%b;
if(t==){
printf("Case %d: divisible\n",++ca);
}
else{
printf("Case %d: not divisible\n",++ca);
}
} return ;
}
c3.直接写也挺好啊~网上代码。里面的res也得用long long。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; char str[];
long long mod; int main()
{
int t;
scanf("%d",&t);
int cas = ;
while( t-- )
{
scanf("%s %lld",str,&mod);
//printf("%s %d\n",str,mod);
int len = strlen( str );
int s = ;
if( str[] == '-' )
s++;
long long res = ;
for( int i = s; i < len; i++ )
{
res = res* + str[i] - '';
res = res % mod;
}
if( !res )
printf("Case %d: divisible\n",++cas);
else
printf("Case %d: not divisible\n",++cas);
}
return ;
}
35 / 62 Problem L LightOJ 1213 Fantasy of a Summation
题意：给你一个求和的循环，让你计算最后的结果是多少？
思路：首先，我们得明确在这个循环里面，a[0]……a[n-1]出现的次数是一样多的，
它大的累加的次数为n^k次方。
看第二个样例：
它有2个数字，3层循环
1、a[0] a[0] a[0]
2、a[0] a[0] a[1]
3、a[0] a[1] a[0]
4、a[0] a[1] a[1]
5、a[1] a[0] a[0]
6、a[1] a[0] a[1]
7、a[1] a[1] a[0]
8、a[1] a[1] a[1]
在这里面它的大的累加次数为2^3=8次，因为每个数的累加次数一样多的
它每个数的累加次数为(n^k)*k/n=(n^(k-1))*k,
则和就等于(sum(a[i])*(n^(k-1))*k)%mod
#include<stdio.h>
long long pow(int a,int n,int mod){
if(n==) return ;
long long t=pow(a,n/,mod);
t=t%mod;
long long ans=t*t%mod;
if(n%==) ans=(ans*(a%mod))%mod;
return ans;
}
int main(){
int T,kase=;
int a[];
scanf("%d",&T);
while(T--){
int n,k,mod;
long long ans=;
scanf("%d%d%d",&n,&k,&mod);
for(int i=;i<n;i++){
scanf("%d",&a[i]);
ans=(ans+a[i]%mod)%mod;
}
long long t=pow(n,k-,mod);
ans=((ans*(k%mod)%mod)*t)%mod;
printf("Case %d: %lld\n",++kase,ans);
}
return ;
}
41 / 137 Problem M LightOJ 1197 Help Hanzo
给你a和b求a到b之间的素数个数。
先在小区间素数筛，大区间就用类似素数筛的想法，把a到b之间不是素数的标记出来。因为b-a最多1e5的大小，所以每组数据的时间复杂度最多就o(1e5 log1e5)。
ps：我感觉这个复杂度为O(1e5+log1e5)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 2e5 + ;
typedef long long LL;
bool prime[MAXN] , vis[MAXN];
LL p[MAXN / ]; void init() {
prime[] = true;
int cont = ;
for(int i = ; i < MAXN ; i++) {
if(!prime[i]) {
p[++cont] = i;
for(int j = i * ; j < MAXN ; j += i)
prime[j] = true;
}
}
} int main()
{
init();
int t , a , b;
scanf("%d" , &t);
for(int ca = ; ca <= t ; ca++) {
scanf("%d %d" , &a , &b);
int res = ;
if(b < MAXN) {
for(int i = a ; i <= b ; i++) {
if(!prime[i])
res++;
}
}
else {
memset(vis , false , sizeof(vis));
for(int i = ; p[i]*p[i] <= b ; i++) {
LL k = a / p[i];
if(k*p[i] < a)
k++;
if(k == ) //此时a%p[i]==0 && a/p[i]==1，说明a刚好是一个素数
k++;
while(k * p[i] <= b) { //筛选a~b中不是素数的
vis[k*p[i] - a] = true;
k++;
}
}
for(int i = a ; i <= b ; i++) {
if(!vis[i - a])
res++;
}
}
printf("Case %d: %d\n" , ca , res);
}
}
45 / 100 Problem N LightOJ 1138 Trailing Zeroes (III)
d.给一个Q，代表N！末尾有Q个0。给出Q，找到最小的N。
s.可以用二分法，找到最小的N。
然后看看怎么求N！后面有几个0？
有算数基本定理可知 N！可划分为质因数相乘的形式 n!=2x*3y*5z*...
因为只有2*5才会出现0，又因为2的个数比5多（可见下面证明），所以N！后面的0的个数就是N！的分解中的5的个数。
那么如何求一个数的阶乘的结果5的幂次方是多少。
譬如30！的结果中，5的幂究竟是多少，答案是30/5 = 6， 6/5 = 1；结果为7个。除到最后的数<5为止。可以自己在纸上验证。
证明：2的个数比5多
对n!做质因数分解n!=2x*3y*5z*...
显然0的个数等于min(x,z)，并且min(x,z)==z
对于阶乘而言，也就是1*2*3*...*n
[n/k]代表1~n中能被k整除的个数
那么很显然
[n/2] > [n/5] (左边是逢2增1，右边是逢5增1)
[n/2^2] > [n/5^2](左边是逢4增1，右边是逢25增1)
……
[n/2^p] > [n/5^p](左边是逢2^p增1，右边是逢5^p增1)
随着幂次p的上升，出现2^p的概率会远大于出现5^p的概率。
因此左边的加和一定大于右边的加和，也就是n!质因数分解中，2的次幂一定大于5的次幂。
#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm> using namespace std; typedef long long LL; LL solve(LL n)
{
LL num=;
while(n)
{
num+=n/;
n/=;
}
return num;
} LL er(LL n)
{
LL x=;
LL y=0x3f3f3f3f;
LL mid;
LL res=-;
while(x<=y)
{
mid=(x+y)/;
LL ans=solve(mid);
if(ans==n)
{
res=mid;
y=mid-;
//return mid;
}
else if(ans>n)
{
y=mid-;
}
else if(ans<n)
{
x=mid+;
}
}
return res;
}
int main()
{ int t;
scanf("%d",&t);
int xp=;
while(t--)
{
LL n;
scanf("%lld",&n);
LL ans=er(n);
if(ans==-) printf("Case %d: impossible\n",xp++);
else printf("Case %d: %lld\n",xp++,ans);
}
return ;
}
37 / 48 Problem O UVA 11426 GCD - Extreme (II)
d.
G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
G+=gcd(i,j);
}
求G。
s.假设a、b(a<b)互质，那么gcd(a,b)=1，这样当i循环到a、j循环到b时就会向结果中+1，而i循环到2*a、j循环到2*b时就会向结果中+2（gcd(2*a,2*b)=2）...循环到k*a和k*b时就会向结果中+k。这样实际上引起结果变化的根源就在于各对互质的数，当i、j循环到他们自身或者自身的倍数时就会引起结果的改变，那么我们不妨先将每对互质的数对结果的贡献值算出来，最后将各对互质的数对结果的贡献累加起来就可以了。
假设和b互质的数有n个，也就是n对(?,b)（?和b互质），那么在i、j循环到?、b时结果会增加n，循环到(2*?,2*b)时结果就会增加2*n...当i、j循环到k*?、k*b时结果就会增加k*n。那么我们不妨用a[i]记录各种k、b在满足k*b=i时会增加多少结果，a[i]代表gcd(x,i)的和，其中x小于i，那么最后我们要输出的就是a[2]+a[3]+...+a[N]。
至于找和b互质的数，就是计算b的欧拉函数的值，然后暴力循环k，并修改对应的a[k*b]即可，整体的复杂度是O(N*logN)的。
欧拉函数扩展： 欧拉公式的延伸：小于n 与n互质的数的和 是euler(n)*n/2
//欧拉函数复杂度O(nlogn)
#include<stdio.h>
#include<string.h>
#include <iostream>
using namespace std;
#define MAXD 4000010
const int N = ;
typedef long long LL;
int phi[MAXD];
LL a[MAXD]; void prep()
{
memset(a, , sizeof(a));
for(int i = ; i <= N; i ++)
phi[i] = i;
for(int i = ; i <= N; i ++)
{
if(phi[i] == i){ ///质数
for(int j = i; j <= N; j += i){
phi[j] = phi[j] / i * (i - );
}
}
for(int j = ; j * i <= N; j ++)
a[j * i] += j * phi[i]; ///通过对i*j的质因子来求
}
for(int i = ; i <= N; i ++)
a[i] += a[i - ];
} int main()
{
prep();
int n;
while(scanf("%d", &n), n)
printf("%lld\n", a[n]);
return ;
}
13 / 65 Problem P UVA 11754 Code Feat
9 / 26 Problem Q UVA 11916 Emoogle Grid
36 / 86 Problem R POJ 1061 青蛙的约会
s.设A在后，B在前，当A与B相遇时，满足：(m-n)*X=(y-x)+L*Y;X是时间，Y是圈数。
移项：(m-n)*X-L*Y=(y-x);
令a=m-n,b=-L，d=gcd(a,b)。则(y-x)%d==0时有解，否则无解。
求出特解，再求最小的X即可。
/*
扩展欧几里德算法（求ax+by=gcd的解以及逆元）
*/
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std; //返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
long long extend_gcd(long long a,long long b,long long &x,long long &y){
if(a==&&b==)return -;//无最大公约数
if(b==){x=;y=;return a;}
long long d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
} int main(){ int x,y,m,n,L;
long long a,b,x0,y0,d;
long long abs_bd; while(~scanf("%d%d%d%d%d",&x,&y,&m,&n,&L)){
a=m-n;
b=-L;
d=extend_gcd(a,b,x0,y0); abs_bd=abs(b/d); if((y-x)%d==){
x0=(x0*((y-x)/d))%b;
//x0=(x0%(b/d)+(b/d))%(b/d);
x0=(x0%abs_bd+abs_bd)%abs_bd;
printf("%lld\n",x0);
}
else{
printf("Impossible\n");
}
} return ;
}
24 / 63 Problem S POJ 2115 C Looooops
hint:见之前博客
13 / 35 Problem T POJ 2116 Death to Binary?
61 / 122 Problem U HDU 2161 Primes
输入n，是素数输出yes，不是则输出no。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std; int p[]; int main()
{
int n,k=;
memset(p,-,sizeof(p));
p[]=;
p[]=;
for(int i=; i<=; i++)
{
for(int j=; j<=sqrt(i); j++)
{
if(i%j==)
{
p[i]=;
break;
}
}
} while(~scanf("%d",&n))
{
if(n<=)
return ;
if(p[n]==-)
printf("%d: yes\n",++k);
else
printf("%d: no\n",++k);
} return ;
}
32 / 87 Problem V UVA 11827 Maximum GCD
题意：给你一组数，求出其中两两最大公约数中最大的值。
思路：数据较小，直接枚举。
#include<stdio.h>
int gcd(int a,int b){//求最大公约数
return b?gcd(b,a%b):a;
}
int main(){
int T;
int a[];
char c;
scanf("%d",&T);
while (getchar() != '\n');
while(T--){
int cnt=;
while((c=getchar())!='\n'){
if(c>='' && c<=''){
ungetc(c,stdin);//将字符c退回到输入流中
scanf("%d",&a[cnt++]);
}
}
int max=;
for(int i=;i<cnt-;i++){
for(int j=i+;j<cnt;j++){
int t=gcd(a[i],a[j]);
if(t>max) max=t;
}
}
printf("%d\n",max);
}
return ;
}
25 / 98 Problem W UVA 10200 Prime Time
题意：通过公式计算出一个数，判断这个数是否为素数。在区间[a,b]上通过公式算出素数占总数的百分比。
ps：里面加上1e-8是什么梗
#include <stdio.h>
#include <string.h>
int prime(int n)
{
int i;
for(i=;i*i<=n;i++)
{
if((n%i)==)
return ;
}
return ;
}
int main()
{
int num[];
int i;
int a,b;
int sum;
memset(num,,sizeof(num));
for(i=;i<=;i++)
num[i]=prime(i*i+i+);
while(scanf("%d%d",&a,&b)!=-)
{
sum=;
for(i=a;i<=b;i++)
sum+=num[i];
printf("%.2f\n",sum*1.0/(b-a+)*+1e-);//精度
}
return ;
}
20 / 154 Problem X SGU 106 The equation
34 / 51 Problem Y POJ 2478 Farey Sequence
题意：给定一个数n，求小于或等于n的数中两两互质组成的真分数的个数。 表达的有点挫，很直接的欧拉函数的应用。
phi(x) 表示与x互质且小于x的正整数的个数。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define see(x) cout<<#x<<":"<<x<<endl;
#define MAXN 1000005
using namespace std; int prime[MAXN],phi[MAXN];
bool notp[MAXN];
void Prime(){
int i, j, np=;
phi[] = ;
memset(notp,false,sizeof(notp));
for(i=;i<MAXN;i++){
if(notp[i]==false){
prime[np++] = i;
phi[i] = i-;
}
for(j=;j<np&&i*prime[j]<MAXN;j++){
notp[i*prime[j]] = true;
if(i%prime[j]==){
phi[i*prime[j]] = phi[i]*prime[j];
break;
}
else{
phi[i*prime[j]] = phi[i]*(prime[j]-);
}
}
}
} long long ans[MAXN];
int main(){
int n, i;
Prime();
ans[] = ;
for(i=;i<MAXN;i++){
ans[i] = ans[i-] + phi[i];
}
while(scanf("%d",&n)&&n){
cout<<ans[n]<<endl;
}
return ;
}
这里要说到关于筛素数的方法。以下算法复杂度为O(n)
void Prime(){
int i, j, np=;
memset(notp,false,sizeof(notp));
for(i=;i<MAXN;i++){
if(notp[i]==false){
prime[np++] = i;
}
for(j=;j<np&&i*prime[j]<MAXN;j++){
notp[i*prime[j]] = true;
if(i%prime[j]==){ //O(n)的关键
break;
}
}
}
}
适时跳出，大大降低了算法复杂度。本质就是任意一个合数都有一个最小质因数，最终被赋值为true时，都是由其的最小质因数筛出来的，其被筛出来后也无需再关心其他数了。
原因如下：设 i 的最小质因数为p[j]，则 i%p[j]==0，设k=i/p[j]，w=i*p[j]=k*p[j]*p[j]，w是由k*p[j]和p[j]共同筛出来的，对于比w更大的也有因子p[j]的数ww，则自然可以由后面的m*p[j](m>k)和p[j]共同筛出来了。
对筛素数的代码，略加几行代码，就可以顺带求出欧拉函数phi[x]了。用到了递推式：
对于p|x。若p2|x，则phi(x) = phi(x/p)*p；否则phi(x) = phi(x/p)*(p-1)
23 / 63 Problem Z UVA 11752 The Super Powers
题目大意：没有输入，找出所有的超级数，超级数即可以拆分成至少两个数的幂形式。
解题思路：先用素数筛选法找出64以内的合数，以为只有幂是合数才可以进行拆分。然后枚举底数进行判断，所有小于2^64-1的数都是满足的，这里有一个技巧，就是说2^64-1已经是unsign long long 的最大值了，那么超过它的数就会变成负数。但其实i的最大次幂是可以求的，x = logi(2^64-1) = log(2^64-1) / log(i);
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <set>
#include <algorithm> using namespace std;
typedef unsigned long long ll;
const int N = ;
int g, v[N], a[N]; void init () {
g = ;
memset(v, , sizeof(v)); for (int i = ; i <= ; i++) {
if (v[i]) {
a[g++] = i;
continue;
} for (int j = i * ; j <= ; j += i) v[j] = ;
}
} void solve () {
set<ll> ans;
ans.insert(); ll MaxT = <<;
for (ll i = ; i < MaxT; i++) {
int ti = ceil( * log() / log(i)) - ;
ll now = i * i * i * i;
ans.insert(now);
for (int j = ; a[j] <= ti; j++) {
now *= (a[j] - a[j-] == ? i : i * i);
ans.insert (now);
}
} for (set<ll>::iterator i = ans.begin(); i != ans.end(); i++)
printf("%llu\n", *i);
} int main () {
init();
solve ();
return ;
}