2017多校联合三／hdu6063 ( RXD and math )快速幂＋思维

本文主要是介绍2017多校联合三／hdu6063 ( RXD and math )快速幂＋思维，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

RXD and math

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 310 Accepted Submission(s): 160

Problem Description

RXD is a good mathematician.
One day he wants to calculate:

\sum i = 1 n k μ 2 (i) \times ⌊ n k i ‾ ‾ ‾ \sqrt ⌋

output the answer module

109+7 .

1≤n,k≤1018

μ (n) = 1 (n = 1)

μ (n) = (- 1) k (n = p 1 p 2 \dots p k)

μ (n) = 0 (o t h e r w i s e)

p1,p2,p3…pk are different prime numbers

Input

There are several test cases, please keep reading until EOF.
There are exact 10000 cases.
For each test case, there are 2 numbers

n,k .

Output

For each test case, output "Case #x: y", which means the test case number and the answer.

Sample Input

  10 10

Sample Output

  Case #1: 999999937

Source

2017 Multi-University Training Contest - Team 3

注意到一个数字 $x$ 必然会被唯一表示成 $a^2\times b$ 的形式.其中 $|\mu(b)| = 1$ 。所以这个式子会把 $n^k]$ 的每个整数恰好算一次. 所以答案就是 $n^k$ ,快速幂即可. 时间复杂度 $O(\log k)$ .

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <list>
#include <bitset>
#include <stack>
#include <stdlib.h>
#define lowbit(x) (x&-x)
#define e exp(1.0)
//ios::sync_with_stdio(false);
//    auto start = clock();
//    cout << (clock() - start) / (double)CLOCKS_PER_SEC;
typedef long long ll;
typedef long long LL;
const int mod=1e9+7;
using namespace std;ll qmod(ll n,ll k)
{ll ans=1;n=n%mod;while(k){if(k%2==0){n=n*n%mod;k/=2;}else{ans=ans*n%mod;k--;}}return ans;
}
int main()
{ll n,k;int cas=1;while(cin>>n>>k){cout<<"Case #"<<cas++<<": "<<qmod(n,k)<<endl;}return 0;
}

这篇关于2017多校联合三／hdu6063 ( RXD and math )快速幂＋思维的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！