请选择 进入手机版 | 继续访问电脑版

全国大学生算法设计与编程挑战赛 (秋季赛)——正式赛 | A: 小x

[复制链接]
云韵 发表于 2020-12-31 18:06:56 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
小x的奇遇-adventure

Description
 
小x是一个热爱生活的人。
小x在「九曲十八弯」中玩的很嗨,但是在最后一次搭车途中被坏人抓走了!得知小x是某「高」校的「高材生」后,邪恶的坏人掏出了罪恶之极的数学题!
坏人A手中有一个函数 ff ,据坏人粗糙的形貌,小x得知,\begin{aligned}f(1)=1,f(n)=\sum_{i=1}^{n-1}[gcd(i,n-i)==1]\end{aligned}f(1)=1,f(n)=i=1∑n−1​[gcd(i,n−i)==1]​
呵,就这?
坏人B手中有一个函数 gg,据坏人粗糙的形貌,小x得知,\begin{aligned}g(n)=\sum_{d|n}f(\frac n d)\end{aligned}g(n)=d∣n∑​f(dn​)​
呵,就这?
小x洋洋自得不到半分钟,被告知坏人A和B只是个传话的,据坏人C粗糙的形貌,小x得知,坏人团体想让小x求出一个新的函数G_k(n)Gk​(n)

救救小x!小x尚有1200字的读书陈诉没写!
Input
 
第一行给出一个整数TT,表示共有TT组测试数据。
对于每组测试数据:
输入仅一行,两个整数 n,kn,k
T\leq10^3T≤103,n,k\leq 10^{12}n,k≤1012,\sum n\leq 10^{12}∑n≤1012,\sum k\leq 10^{12}∑k≤1012
Output
 
对于每组测试数据:
输出G_k(n) \mod 1e9+7Gk​(n)mod1e9+7。
Sample Input 1 
  1. 27 510 2
复制代码
Sample Output 1
  1. 14
复制代码
Sample Input 2 
  1. 23 11 1
复制代码
Sample Output 2
  1. 21
复制代码
源码:

[code]#include#define fi first#define se second#define mid (l+r>>1)#define endl '\n'using namespace std;typedef long long ll;typedef pairpii;typedef vectorvi;struct tri {int a, b, c;};const int N = 5e6 + 10;const int inf = 0x3f3f3f3f;const ll linf = 0x3f3f3f3f3f3f3f3f;const ll mod = 1e9 + 7;ll prime[N];ll f(ll a){    ll ret=1;    for(int i=1;prime*prime>n>>k;    if(n==0)return 0;    if(k==0)return n;    k=(k+1)/2;    for(int i=0;i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )