Codeforces Round #729 (Div. 2) c题

向右看齐 2022-10-12 05:25 179阅读 0赞

[https://codeforces.com/contest/1542/problem/C][https_codeforces.com_contest_1542_problem_C]

--------------------

## 题目大意 ##

定义 f ( i ) f(i) f(i) 为不能整除  i i i 的正整数， 例如 f ( 1 ) = 2 f(1) = 2 f(1)=2， f ( 2 ) = 3 f(2) = 3 f(2)=3，求 f ( 1 ) + f ( 2 ) + . . . + f ( n ) f(1)+f(2)+...+f(n) f(1)\+f(2)\+...\+f(n)

--------------------

## 题解 ##

先求 1 1 1到 i − 1 i-1 i−1 的最小公倍数，最大数不超过 1 e 16 1e^\{16\} 1e16

`ans = 2 * n % mod;`  
`ans=(ans+n/pre[i]);`

--------------------

## 代码 ##

#include<bits/stdc++.h>
    using namespace std;
    #define re register int
    #define int long long
    inline int read()
    { 
    	int x=0,f=1;char ch=getchar();
    	while(!isdigit(ch)){ if(ch=='-')f=-1;ch=getchar();}
    	while(isdigit(ch)){ x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    	return f==1?x:-x;
    }
    const int maxn=1e16+10,modp=1e9+7;
    int gcd(int x,int y)
    { 
    	return !y?x:gcd(y,x%y);
    }
    int Lcm[50]; 
    signed main()
    { 
    	int tmp=1,x=1;
    	while(1)
    	{ 
    		Lcm[tmp]=x;
    		x=x*tmp/gcd(x,tmp);
    		if(x>maxn)break;
    		tmp++;
    	}
    	//cout << tmp<<endl;
        //for(re i=1;i<=tmp;++i)cout<<Lcm[i]<<" ";
    	int T=read();
    	while(T--)
    	{ 
    		int n=read(),ans=2*n%modp;
    		for(re i=3;i<=tmp;++i)
    			ans=(ans+n/Lcm[i])%modp;
    		printf("%lld\n",ans);
    	}
    	return 0;
    }

大佬的代码搬过来了，侵删！

[https_codeforces.com_contest_1542_problem_C]: https://codeforces.com/contest/1542/problem/C

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #663 (Div. 2) B题

[题目链接][Link 1] include <cstdio> include <iostream> using namespace std

àì夳堔傛蜴生んèń/ 2022年11月26日 07:38/ 0 赞/ 162 阅读

相关 Codeforces Round #663 (Div. 2) A题

[题目链接][Link 1] 这是一道简单题，我当时构造了一种剩余最大，剩余最小，轮番输出的方式，来实现了题目中的要求。实际上好像还有更简单的方式，直接从大到小输出，或者

朱雀/ 2022年11月26日 01:43/ 0 赞/ 202 阅读

相关 Codeforces Round #729 (Div. 2) c题

[https://codeforces.com/contest/1542/problem/C][https_codeforces.com_contest_1542_proble

向右看齐/ 2022年10月12日 05:25/ 0 赞/ 180 阅读

相关 Codeforces Round #728 (Div. 2)a-c

https://codeforc.es/contest/1541 cf a b c a 给定一个数n，1 2 3 4 … n

比眉伴天荒/ 2022年10月10日 04:48/ 0 赞/ 4 阅读

相关 Codeforces Round 374 div2

题目链接： [ CodeforcesRound374][CodeforcesRound374] 做了这么久cf了，，c题有时候还是做不起，，真的好菜，，，，

Dear 丶/ 2022年07月16日 03:38/ 0 赞/ 180 阅读

相关 Codeforces Round #118 (Div. 2) C. Plant

Dwarfs have planted a very interesting plant, which is a triangle directed "upwards". Th

蔚落/ 2022年05月17日 01:13/ 0 赞/ 198 阅读

相关 Codeforces Round #556 (Div. 2) A题

题面很简单，思路就是简单贪心，si数组是贮存购买数组，bi数组是贮存出售数组，题面是给你r的货币，让你通过出售和购买来获取最大价值，第一种算法是通过找出bi数组最大值，和si数

川长思鸟来/ 2022年01月09日 06:47/ 0 赞/ 206 阅读

相关 Codeforces Round #556 (Div. 2) A题

题面很简单，思路就是简单贪心，si数组是贮存购买数组，bi数组是贮存出售数组，题面是给你r的货币，让你通过出售和购买来获取最大价值，第一种算法是通过找出bi数组最大值，和si数

怼烎@/ 2021年12月24日 06:13/ 0 赞/ 203 阅读

相关 Codeforces Round #553 (Div. 2)

A：[http://codeforces.com/contest/1151/problem/A][http_codeforces.com_contest_1151_proble

た入场券/ 2021年11月04日 13:36/ 0 赞/ 261 阅读

相关 Codeforces Round #573 (Div. 2)

<table> <thead> <tr> <th>Sloved</th> <th align="center">A</th> <th alig

浅浅的花香味﹌/ 2021年09月29日 13:10/ 0 赞/ 269 阅读