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.

Delete this entry (admin only).