小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
Sample Output 1
Sample Input 2
Sample Output 2
源码:
[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 |