想用分治做,但是T了。
  • 板块P2424 约数和
  • 楼主_加零_
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/1/4 11:26
  • 上次更新2024/1/4 17:03:15
查看原帖
想用分治做,但是T了。
502530
_加零_楼主2024/1/4 11:26

求优化,拜谢/bx

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
#define int long long
int a,b;
template<typename T>
inline void read(T&x){
	T ans=0,w=1;
	char ch;
	while((ch=getchar())<'0'||ch>'9') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') ans=(ans<<3)+(ans<<1)+(ch^'0'),ch=getchar();
	x=ans*w;
}
template<typename T>
inline void write(T x,char ch=0){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
	if(ch) putchar(ch);
}
int ksm(int a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a;
		a=a*a;
	}
	return ans;
}
int sum(int p,int c){
	if(c==0){
		return 1;
	}else if(c&1)return (1+ksm(p,(c+1)/2))*sum(p,(c-1)/2);
	else{
		return (1+ksm(p,c/2))*sum(p,c/2-1)+ksm(p,c);	
	}
}
int devide(int n){
	int p[maxn],c[maxn];
	int m=0;
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			p[++m]=i;c[m]=0;
			while(n%i==0){
				c[m]++;
				n/=i;
			}
		}
	}
	if(n>1){
		p[++m]=n;
		c[m]=1;
	}
	int ans=1;
	for(int i=1;i<=m;i++){
		ans*=sum(p[i],c[i]);
	}
	return ans;
}
signed main(){
	read(a),read(b);
	int wa=0;
	for(int i=a;i<=b;i++){
        //cout << devide(i) << endl;
		wa+=devide(i);
	}
	write(wa,'\n');
    //cout << devide(b)-devide(a-1);
	return 0;
}
2024/1/4 11:26
加载中...