3
26
2016
0

[vp]Codeforces Round #323 (Div. 1)

真不该作选了场$div1$打,你tm有空打vp怎么不去填坑!

这场的感觉十分玄妙,现场的话估计不会写$C$会去插人

$Claris$都是看了$C$和$D$然后决定跑不跑路...然而我太弱了就按$A$->$B$->$C$的顺序做下去

Category: codeforces | Tags: gcd codeforces vp
12
28
2015
1

[bzoj]4373: 算术天才⑨与等差数列

-->http://www.lydsy.com/JudgeOnline/problem.php?id=4373

强制在线。。只能想到数据结构-。-

标算表示想不到-。-||| %Claris

我的做法是,用线段树维护区间最小值,区间哈希值,哈希采用平方和的方法(from 比利),对于一个知道了首项和公差的等差数列,其数列

$hash 值= n·a[1]·a[n]+ \frac{n(n-1)(2n-1)·k^2}{6}$

然后。。

Category: bzoj | Tags: hash gcd 线段树
12
25
2015
0

[bzoj]2226: [Spoj 5971] LCMSum

-->http://www.lydsy.com/JudgeOnline/problem.php?id=2226

 

跟比利做题时不时就会出现这种我还没做过的题$0.0$

$O(T\sqrt n)$

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000010
#define ll long long
int i,j,k,m,n,x,y,T,phi[N],o;ll ans;
int main(){
	phi[1]=1;
	for(i=2;i<=N;++i)if(!phi[i])for(j=i;j<=N;j+=i){
		if(!phi[j])phi[j]=j;
		phi[j]=phi[j]/i*(i-1);
	}
	for(ans=0,T=read();T--;){
		for(ans=0,n=read(),o=sqrt(n),i=1;i<=o;++i)if(n%i==0){
			if(i!=1)ans+=1ll*i*phi[i]/2;
			else ans+=1;
			if(i*i!=n)ans+=1ll*n/i*phi[n/i]/2;
		}
		printf("%lld\n",1ll*ans*n);
	}
}

 

Category: bzoj | Tags: gcd 数论

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com