# Demo entry 6346667

Utop

Submitted by anonymous on Feb 12, 2017 at 05:23
Language: C++. Code size: 1.5 kB.

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int mod = 1e9 + 7;
int a[500], b[500];
int tot, n;
long long fin[1000010], limit, ans;
void factor(int nn)
{
int tmp,i,now;
tmp = (int)((double)sqrt(nn*1.0) + 1);
tot = 0;
now = nn;
for(i=2;i<=tmp;++i)
{
if(now % i == 0)
{
a[++tot] = i;
b[tot] = 0;
while(now % i == 0)
{
++b[tot];
now /= i;
}
}
}
if(now != 1)
{
a[++tot] = now;
b[tot] = 1;
}
}
long long cal(long long l, long long r, int k)
{
return r/k-(l-1)/k;
}
void dfs(int idx, int k, int num)
{
if(idx > tot)
{
if(k == 1)  return;
if(num % 2) (ans -= cal(n, limit, k))%=mod;
else    (ans += cal(n, limit, k))%=mod;
return;
}
dfs(idx+1, k, num);
dfs(idx+1, k*a[idx], num+1);
}
void init()
{
for(int i=1;i<=1000000;i++)
{
factor(i);
limit = (long long)i*i;
n = i;
ans = limit-n+1;
dfs(1, 1, 0);
fin[i] = ans;
(fin[i] += fin[i-1]) %= mod;
}
}
int main()
{
init();
int t;
scanf("%d",&t);
for(int ica=1;ica<=t && scanf("%d",&n);ica++)
{
fin[n] = fin[n] % mod;
fin[n] += mod;
fin[n] = fin[n] % mod;
printf("Case #%d: %lld\n",ica, fin[n]);
}
}
```

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.