kmjp's blog

競技プログラミング参加記です

diverta 2019 Programming Contest : D - DivRem Number

すごい悪い出来というわけではないのだが、反省点はあったな。
https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d

問題

正整数Nが与えられる。
Nをmで割った商と余りが一致するようなmの総和を求めよ。

解法

商や余りをxを置くとN=m*x+x=(m+1)xなので、m+1はNの約数である。
ということでNの約数からmを列挙し、条件を満たすか判定すればよい。
x<(m+1)でなければいけないので、無条件に(Nの約数-1)の総和を取るのは止めること。

ll N;

ll hoge(ll v) {
	v--;
	if(v && N%v==N/v) {
		return v;
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	for(ll a=1;a*a<=N;a++) if(N%a==0) {
		ret+=hoge(a);
		if(a*a!=N) ret+=hoge(N/a);
	}
	cout<<ret<<endl;
	
}

まとめ

これは実装軽いし400ptでもよさそうね。