请问这题要高精度吗
  • 板块P6583 回首过去
  • 楼主八水L
  • 当前回复11
  • 已保存回复11
  • 发布时间2020/5/31 21:56
  • 上次更新2023/11/7 01:20:44
查看原帖
请问这题要高精度吗
87458
八水L楼主2020/5/31 21:56

rt,如果不要的话,有没有大佬帮忙看下代码的问题(可能有些凌乱)

#include<bits/stdc++.h>
#define ll long long
const int N=1e6+1e5;
using namespace std;
ll n,ans; int ct,cnt,fla;
ll a[N][5],e[N];
struct nod{
	ll x;
	int y;
}P[N];
bool operator<(nod aa,nod bb){
	return aa.x<bb.x;
}
ll Qiu(ll x,int vis){
	if(vis==1)
		return x-x/2-x/5+x/10;
	else if(vis==2) return x-x/2;
	else if(vis==3) return x-x/5;
	else return x;
}
ll Query(ll x){
	if(!(x%2)&&!(x%5))
		{ fla=1; return x-x/2-x/5+x/10; }
	else if(!(x%2)) { fla=2; return x-x/2; }
	else if(!(x%5)) { fla=3; return x-x/5; }
	else { fla=4; return x; }
}
void zcfk_be(){
	ct=0;
	for(ll l=1,r;l<=n;l=r+1){
		++ct,r=n/(n/l),e[ct]=n/l;
		a[ct][1]=(n/l)*(Qiu(r,1)-Qiu(l-1,1));
		a[ct][2]=(n/l)*(Qiu(r,2)-Qiu(l-1,2));
		a[ct][3]=(n/l)*(Qiu(r,3)-Qiu(l-1,3));
		a[ct][4]=(n/l)*(Qiu(r,4)-Qiu(l-1,4));
//		cout<<e[ct]<<" "<<a[ct][1]<<" "<<a[ct][2]<<" "<<a[ct][3]<<" "<<a[ct][4]<<endl;
	}
	for(int i=ct;i>=1;i--)
		a[i][1]+=a[i+1][1],a[i][2]+=a[i+1][2],a[i][3]+=a[i+1][3],a[i][4]+=a[i+1][4];
}
void zcfk(ll x){
	ll l=x+1,r;
	if(l>n) return ;
	r=n/(n/l),ans+=(n/l)*(Qiu(r,fla)-Qiu(l-1,fla));
	P[++cnt].x=n/(r+1); P[cnt].y=fla;
//	cout<<n/(r+1)<<":zcfk:"<<fla<<endl;
}
int main(){
	ll x=1,y=1,sum=0;
	scanf("%lld",&n);
	zcfk_be();
	for(int i=0;i<=40;i++){ y=1;
		for(int j=0;j<=20;j++){ sum=0;
			if(x*y>n) break;
			sum=Query(x*y);
			ans+=sum*(n/(x*y));
			zcfk(x*y); y*=5;
		}
		x*=2;
	}
	sort(P+1,P+1+cnt);
	for(int i=1,j=ct;i<=cnt;i++){
		while(P[i].x>e[j]&&j>1) j--;
//		cout<<P[i].x<<" "<<e[j]<<endl;
		if(P[i].x==e[j]) ans+=a[j][P[i].y];//,cout<<a[j][P[i].y]<<endl;
	}
	printf("%lld\n",ans);
	return 0;
}
2020/5/31 21:56
加载中...