【SPOJ】DIVCNTK min

题目大意

　　给你 \(n,k\)，求

\[S_k(n)=\sum_{i=1}^n\sigma_0(i^k) \]

　　对 \(2^{64}\) 取模。

题解

　　一个min_25筛模板题。

　　令 \(f(n)=\sigma_0(n^k)\)，那么 \(S_k(n)=\sum_{i=1}^nf(i)\)，而且

\[\begin{cases} f(1)&=1\\ f(p)&=k+1\\ f(p^c)&=kc+1 \end{cases} \]

　　直接上min_25筛就好了。

　　时间复杂度：\(O(\frac{n^\frac{3}{4}}{\log n})\)

　　某些实现可能会有一点微小的细节。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<functional>
#include<cmath>
#include<assert.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void open(const char *s){
#ifndef ONLINE_JUDGE
	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}
void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}
int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}
int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}
const int M=100010;
int pri[M],cnt,b[M];
ll f1[M],f2[M];
void init()
{
	for(int i=2;i<=100000;i++)
	{
		if(!b[i])
			pri[++cnt]=i;
		for(int j=1;j<=cnt&&i*pri[j]<=100000;j++)
		{
			b[i*pri[j]]=1;
			if(i%pri[j]==0)
				break;
		}
	}
	pri[cnt+1]=100001;
}
ll n,k;
int m;
ll dfs(ll x,int y)
{
	if(x<=1||x<pri[y])
		return 0;
	if(pri[y]>m)
		return (x<=m?f1[x]:f2[n/x])-f1[m];
	ll s=(x<=m?f1[x]:f2[n/x])-f1[pri[y]-1];
	for(int i=y;i<=cnt&&(ll)pri[i]*pri[i]<=x;i++)
	{
		ll x1=x/pri[i];
		for(int j=1;x1>=pri[i];j++,x1/=pri[i])
			s+=dfs(x1,i+1)*(j*k+1)+((j+1)*k+1);
	}
	return s;
}
void solve()
{
	scanf("%lld%lld",&n,&k);
	m=sqrt(n)+0.5;
	int mx=n/(m+1);
	for(int i=2;i<=m;i++)
		f1[i]=i-1;
	for(int i=1;i<=mx;i++)
		f2[i]=n/i-1;
	for(int i=1;i<=cnt&&pri[i]<=m;i++)
	{
		ll x=f1[pri[i]-1];
		int n1=min((ll)mx/pri[i],n/pri[i]/pri[i]);
		int n2=min((ll)mx,n/pri[i]/pri[i]);
		for(int j=1;j<=n1;j++)
			f2[j]-=f2[j*pri[i]]-x;
		for(int j=n1+1;j<=n2;j++)
			f2[j]-=f1[n/j/pri[i]]-x;
		for(int j=m;j>=(ll)pri[i]*pri[i];j--)
			f1[j]-=f1[j/pri[i]]-x;
	}
	for(int i=2;i<=m;i++)
		f1[i]*=k+1;
	for(int i=1;i<=mx;i++)
		f2[i]*=k+1;
	ll ans=dfs(n,1);
	ans++;
	printf("%llu\n",ans);
}
int main()
{
	open("divcntk");
	int t;
	scanf("%d",&t);
	init();
	while(t--)
		solve();
	return 0;
}

转载请注明出处:http://www.hrtxgs.com/article/20230526/680366.html

随机推荐

【SPOJ】DIVCNTK min_25筛
题目大意　　给你 \(n,k\)，求 \[S_k(n)=\sum_{i=1}^n\sigma_0(i^k) \]　　对 \(2^{64}\) 取模。题解　　一个min_25筛模板题。　　令 \(f(n)=\sigma_0(n^k)...
SPOJ TRANSP2
发现第二个矩阵写出来实际上相当于把前\(a\)位和后\(b\)位的优先级换了一下写出来。求的最小交换次数就是\(2^{a+b}-环数\)。在这里可以把一个环看成一个等价类，一个数循环移位\(a\)位之后得到的数和他本身等价。这就转化成一...
佩林-下一个回文- SPOJ问题
我已经为Ridit开了一个帐户，他是在SPOJ学习Java的7岁学生之一。我给他的第一个任务是佩林-The下一个回文。这是这个问题的链接-PALIN- The next Palindrome- SPOJ在我向他解释了这个问题之后，他基本上能...
SPOJ生活宇宙和一切
我正在尝试用Java6(JAR)来解决spoj上的以下问题：你的计划是使用暴力的方法，以便找到生活，宇宙和一切的答案。更准确地说...将小数字从输入重写到输出。读入数字42后停止处理输入。输入的所有数字都是一位或两位数字的整数。输入:1 2...
spoj Minimax Triangulation
题解： dp+计算几何 F[i][j]表示第i-j条边的答案然后转移一下代码： #includebits/stdc++.h using namespace std; struct note{int x,y;}a[55]; int ...
spoj 839-Optimal Marks
Description SPOJ.com - Problem OPTM Solution 容易发现各个位之间互不影响, 因此分开考虑每一位. 考虑题中是怎样的一个限制: 对每个点确定一个0/1的权值; 对于有连边且权值不同的点, 对答案...
在spoj AP2上获得错误的回复
我在回答一个问题SPOJ AP2你将得到第三个学期，第三个最后一个学期和系列的总和。您需要打印系列的长度系列。使用的逻辑- first term+last term=third term + third last termsum=n/2(f...
python的SPOJ中的输入数据是什么类型？我如何在Jupyter notebook中实现它？
我是编程新手，我一直在尝试用SPOJ解决问题。我首先在jupyter笔记本中求解它们以测试它们，然后复制代码。这花费了我大量的尝试和错误。我认为SPOJ输入是标准输入格式，我想我知道如何“阅读”。但是，如果我想尝试其他输入来测试我的代码，我...
【学术篇】SPOJ GEN Text Generator AC自动机+矩阵快速幂
还有5天省选才开始点字符串这棵技能树是不是太晚了点... 题目の传送门 AC自动机不想讲了QAQ.其实很久以前是学过然后打过板子的, 但也仅限于打过板子了~ 之前莫名其妙学了一个指针版的但是好像不能用循环遍历fail好像就啥也干不了于是改...
为什么我的简单代码在spyder上运行良好，但不能在SPOJ的在线IDE上运行？
这是我在SPOJ上的第一个初学者级别问题的代码:将小数字从输入重写到输出。读入数字42后停止处理输入。输入端的所有数字都是一位或两位数字的整数。我的代码：b=[] while True: n=int(input(Enter the ...

成都海润天祥科技有限公司

【SPOJ】DIVCNTK min_25筛

题目大意

题解

代码

随机推荐

相关专题