//约数
/*
求n的正约数集合：试除法
复杂度：O(sqrt(n))
原理：扫描[1,sqrt(N)]，尝试d能否整除n，若能，则N/d也能
*/
int factor[
1600],m=
0;
for(
int i=
1;i*i<=n;i++
){
if(n%i==
0){
factor[++m]=
i;
if(i!=n/i) factor[++m]=n/
i;
}
}
/*
求[1,n]每个数的正约数集合：倍数法
复杂度：O(nlogn)
原理：对于每个数d，[1,n]中以d为约数的数就是d的倍数
*/
vector<
int> factor[
500010];
for(
int i=
1;i<=n;i++
)
for(
int j=
1;i*j<=n;j++
)
factor[i*
j].push_back(i);
/*两个推论
1.一个整数的约数个数上界 为2*sqrt(n)
2.[1,n]每个数的约数个数总和大约为nlogn
*/
/*
题意有点绕
每个人手里有一个非0数字，首先第k个人出列，然后按其手里的数字让下一个人出列
循环如此，设i为小于等于N的最大反素数，问第i个出列的人的编号
打表求反素数：按质因数大小递增顺序搜索每一个质因子，枚举每一个质因子的个数
唯一分解定理，一个数的因子数：(p1+1)(p2+1)(p3+1)...
性质1：一个反素数的质因子必然是从2开始连续的质数
性质2：
1 2 3 4 6 9 12 18 36
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
#define inf 1<<29
int n,p[]={
0,
2,
3,
5,
7,
11,
13,
17,
19,
23,
29,
31},use[
20];
ll maxt,ans;//maxt是最大因子数，ans是当前的反质数
//id是素数表的下标，now是当前数字，tot是因子数,符合因子数公式
void dfs(ll id,ll now,ll tot){
if(tot>maxt)
//找到了因子数更大的数
ans=now,maxt=
tot;
else if(tot==maxt && now<ans)
//找到因子数相同，但是数值更小的数
ans=now,maxt=
tot;
use[id]=
0;
while(now*p[id]<=n && use[id]+
1<=use[id-
1]){
//第二个是剪枝
use[id]++
;
now*=
p[id];
dfs(id+
1,now,tot*(use[id]+
1));
}
}
int main(){
scanf("%d",&
n);
use[0]=
inf;
dfs(1,
1,
1);
printf("%lld",ans);
return 0;
}
推公式题，详见进阶指南p134
思路大概是：当i在区间[x,k/(k/x)]时，k/i的值都是一样的，那么这一段的值可以用等差数列求和公式做
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long n,k;
long long ans;
int main(){
scanf("%lld%lld",&n,&
k);
ans=(
long long)n*
k;
for(
int x=
1,gx=
0;x<=n;x=gx+
1){
gx=k/x?min(n,k/(k/
x)):n;
ans-=(k/x)*(x+gx)*(gx-x+
1)/
2;
//首项x*k/x,末项gx*k/x,项数gx-x+1
}
printf("%lld\n",ans);
}
转载于:https://www.cnblogs.com/zsben991126/p/10232426.html
