読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

abc 020

D問題

abc020.contest.atcoder.jp

 \displaystyle
\sum_{i=1}^{N} lcm(i,K)
を求めよ。

15点解法

ll gcd(ll x, ll y)
{
  if(x == 0 || y == 0) return max(x,y);
  ll a = max(x,y);
  ll b = min(x,y);
  return gcd(a%b,b);
}

ll lcm(ll x, ll y)
{
  return x * y / gcd(x,y);
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  // FROM HERE
  int ans = 0;
  int n, k; cin >> n >> k;
  FOR(i,1,n) ans = (ans + lcm(i,k)) % MOD;
  cout << ans << endl;
  return 0;
}

100点解法

ll gcd(ll x, ll y)
{
  if(x == 0 || y == 0) return max(x,y);
  ll a = max(x,y);
  ll b = min(x,y);
  return gcd(a%b,b);
}
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  // FROM HERE
  ll ans = 0;
  ll n, k; cin >> n >> k;
  FOR(i,1,k)
  {
    ll sum = (n/k+(n%k>=i))*(i+i+(n-i)/k*k)/2;
    ans =  (ans + sum * k / gcd(i,k)) % MOD;
  }
  cout << ans << endl;
  return 0;
}

満点解法

保留(あとで見る)

n,k=map(int,input().split())
 
sums = []
for d in range(1, 100000):
	if d*d > k: break
	if k % d == 0:
		sums.append([d, (n//d)*(n//d+1)//2*d])
		if d * d != k:
			e = k//d
			sums.append([e, (n//e)*(n//e+1)//2*e])
sums.sort()
for i in range(len(sums)-1,-1,-1):
	for j in range(i):
		if sums[i][0] % sums[j][0] == 0:
			sums[j][1] -= sums[i][1]
 
ret = 0
for v in sums:
	ret += v[1]*(k//v[0])
print(ret%1000000007)