忽明忽暗之打表篇

(数论打表篇)

小学生一发

一打打表的题目，反正现在一看到这种题目，打表大法好，我tm什么都不想就想打表(哈哈蛤)。

忽明忽暗

题目描述:
走廊里有$n$n盏灯，编号依次为$1, 2, 3, .... , n,$1,2,3,....,n,由学校电路控制中心管理。初始时，所有灯都是关闭的。某黑客入侵了学校电路的控制中心，黑客相让灯忽明忽暗，进行了$n$n轮操作。第$i$i轮操作，会让所有编号为$i$i的倍数的灯状态反转，也就是打开的变为关闭，关闭的变为打开。

现在黑客想知道，$n$n轮操作后，所有亮着的灯的编号之和为多少。因为答案很大，只需要输出答案对10⁹+7取模的结果。

输入:
一个整数$n$n，表示灯的个数。(s<=10^18)

输出:
一个整数,表示亮着的灯的编号之和对10^9+7取模的结果。

解析

这是一道打表题(仅对本弱渣而言qaq)，首先可以打表发现哪些数是会最后亮着的, 怎么打表呢? 不是很显然吗，这个数的因子个数为奇数最后亮着，为偶数最后会GG。证明是很显然的，这个不用说了，自己想想就知道了。我们玩点有技术含量的吧，通过打表可以发现最后留下来的都是平方数。那么就可以猜测答案为:$\displaystyle\sum_{i=1}^{[\sqrt n]} i^2$i=1∑[n​]​i2，怎么证明呢?
其实也很简单，由素数分解的唯一性可知: $n=p^a_1p^a_2p^a_3...p_a^n$n=p1a​p2a​p3a​...pan​, 易知$n$n的因子数为$\tau (n)=(a_1+1)(a_2+1)...(a_n+1)$τ(n)=(a1​+1)(a2​+1)...(an​+1), 那么如果$\tau(n)$τ(n)如果为奇数，即所有的$a_1, a_2,...a_n$a1​,a2​,...an​均为偶数, 那么表明$their$their都有一个共同的因子$2$2，提出来不就是平方数了。
具体处理，可以知道平方和的公式为$\displaystyle\sum_{i=1}^{n} i^2=n(n+1)(2n+1)/6$i=1∑n​i2=n(n+1)(2n+1)/6, 那么再利用费马小定理取模逆就好了,次方用快速幂即可。

AC代码:

//  小学生一发的刷题之路
//  数论-打表;
//  忽明忽暗
//  打表-费马小定理-快速幂
//


#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>                //双向队列;
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <vector>
#include <cstdlib>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double PI=acos(-1.0);
const double eps=1e-8;
const double e=exp(1.0);
const int maxn=5e5+5;
const int maxm=1e6+5;
const ll mod=1e9+7;
const int INF=1e8;
template<class T>
void read(T &ret){              //快速输入模版;
    ret=0;
    int f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        ret=ret*10+c-'0';
        c=getchar();
    }
    ret*=f;
}
int ans[110];
int devide(int x){
    int ans=0;
    for(int i=1;i<=x;i++)
        if(x%i==0){
            ans++;
        }
    return ans%2;
}

ll poww(ll a,ll b){
    ll ans=1,base=a;
    while(b>0){
        if(b&1){
            ans*=base;
            ans%=mod;
        }
        b>>=1;
        base*=base;
        base%=mod;
    }
    return ans;
}

int main()
{
    ll n;
    scanf("%lld\n",&n);
    ll m=sqrt(n);
    m%=mod;
    ll ans=m*(m+1)%mod;
    ans=ans*(2*m+1)%mod;
    ans=ans*poww(6,mod-2)%mod;
    printf("%lld\n",ans);
    return 0;
}

新的开始，每天都要快乐哈。