首页
登录 | 注册

loj #6053. 简单的函数

#6053. 简单的函数

题目描述

某一天,你发现了一个神奇的函数f(x)f(x)f(x),它满足很多神奇的性质:

  1. f(1)=1f(1)=1f(1)=1。
  2. f(pc)=p⊕cf(p^c)=p \oplus cf(pc​​)=pc(ppp 为质数,⊕\oplus⊕ 表示异或)。
  3. f(ab)=f(a)f(b)f(ab)=f(a)f(b)f(ab)=f(a)f(b)(aaa 与 bbb 互质)。

你看到这个函数之后十分高兴,于是就想要求出 ∑i=1nf(i)\sum\limits_{i=1}^n f(i)i=1n​​f(i)。

由于这个数比较大,你只需要输出 ni=1f(i)mod1000000007。

输入格式

一行一个整数 nnn。

输出格式

一行一个整数 ni=1f(i)mod1000000007。

样例

样例输入 1

6

样例输出 1

16

样例输入 2

233333

样例输出 2

179004642

样例输入3

9876543210

样例输出3

895670833

数据范围与提示

对于30%30\%30%的数据,n≤100n \leq 100n100。
对于60%60\%60%的数据,n≤106n \leq 10^6n106​​。
对于100%100\%100%的数据,1≤n≤10101 \leq n \leq 10^{10}1n1010​​。

 

loj #6053. 简单的函数
loj #6053. 简单的函数
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000010
#define mod 1000000007
using namespace std;
int p[maxn],cnt,n,f[maxn];
bool vis[maxn];
void prepare(){
    for(int i=2;i<=n;i++){
        if(!vis[i])p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<=n;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}
void make(int x){
    int a=1,b=1,now=x;
    for(int i=1;i<=cnt;i++){
        if(now==1)break;
        if(now%p[i]==0){
            if(a==1)
                while(now%p[i]==0)a*=p[i],now/=p[i];
            else 
                while(now%p[i]==0)b*=p[i],now/=p[i];
        }
    }
    f[x]=f[a]*f[b];
}
int main(){
    scanf("%d",&n);prepare();
    memset(f,-1,sizeof(f));
    f[1]=1;
    for(int i=1;i<=cnt;i++){
        int t=0;long long mul=1;
        while(1){
            t++;
            mul=mul*(long long)p[i];
            if(mul>1LL*n)break;
            else f[mul]=p[i]^t;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(f[i]==-1)make(i);
        ans+=f[i];
        if(ans>=mod)ans-=mod;
    }
    printf("%d\n",ans);
    return 0;
}
40分 暴力

 


相关文章

  • 定义函数时,默认参数必须指向不变的对象 参数为可变对象时,正常调用的时候,结果没有问题,但是当使用默认参数的时候,结果就会和理想的有差距. In [78]: def add(L=[]): ...: L.append('END') ...: ...
  • 前言:最近一直在刷leetcode的题,用到isalnum函数,用man手册查找了一下,总共有13个相关函数如下: #include <ctype.h> int isalnum(int c); int isalpha(int c ...
  • 详解linux进程间通信-管道 popen函数 dup2函数
    前言:进程之间交换信息的唯一方法是经由f o r k或e x e c传送打开文件,或通过文件系统.本章将说明进程之间相互通信的其他技术—I P C(InterProcess Communication).今天将介绍半双工的管道. 一.匿名管 ...
  • 目录 什么是闭包?(掌握) 两种为函数传参的方式 闭包函数的应用(掌握) 回顾: 函数对象:可以将定义在函数内的函数返回到全局使用,从而打破函数的层级限制. 名称空间与作用域:作用域关系在函数定义阶段时就已经固定死了,与调用位置无关,即在任 ...
  • More Effective C++
    More Effective C++ 35个改善编程与设计的有效方法 只有深入了解C++编译器如何解释代码, 才有可能用C++语言写出健壮的软件. C++的难学, 不仅在其广博的语法, 语法背后的语义, 语义背后的深层思维, 深层思维背后的 ...
  • 1.什么是跨越? 一个网页向另一个不同域名/不同协议/不同端口的网页请求资源,这就是跨域. 跨域原因产生:在当前域名请求网站中,默认不允许通过ajax请求发送其他域名. 2.为什么会产生跨域请求? 因为浏览器使用了同源策略 3.什么是同源策 ...

2020 cecdns.com webmaster#cecdns.com
12 q. 0.066 s.
京ICP备10005923号