uva12546. LCM Pair Sum
uva12546. LCM Pair Sum
In other words, he needs the sum of all possible pairs whose least common multiple is n. (The least common multiple (LCM) of two numbers p and q is the lowest positive integer which can be perfectly divided by both p and q). For example, there are 5 different pairs having their LCM equal to 6 as (1, 6), (2, 6), (2, 3), (3, 6), (6, 6). So f (6) is calculated as f (6) = (1 + 6) + (2 + 6) + (2 + 3) + (3 + 6) + (6 + 6) = 7 + 8 + 5 + 9 + 12 = 41.
Your friend knows you are good at solving this kind of problems, so he asked you to lend a hand. He also does not want to disturb you much, so to assist you he has factorized the number. He thinks it may help you.
Input
The first line of input will contain the number of test cases T (T500). After that there will be T test cases. Each of the test cases will start with a positive number C (C15) denoting the number of prime factors of n. Then there will be C lines each containing two numbers Pi and ai denoting the prime factor and its power (Pi is a prime between 2 and 1000) and ( 1ai50). All the primes for an input case will be distinct.
Output
For each of the test cases produce one line of output denoting the case number and f (n) modulo 1000000007. See the output for sample input forexact formatting.
Sample Input
3
2
2 1
3 1
2
2 2
3 1
1
5 1
Sample Output
Case 1: 41
Case 2: 117
Case 3: 16
这道题目也也搞了很长时间,算是初识母函数吧,这道题目用到了这种思想。做完了,感觉还是不太明白怎么就能用
(1+a1+a1^2...(c1+1)*a1^c1)*(1+a2+a2^2...(c2+1)*a2^c2)*.....*(1+am+am^2...(cm+1)*am^cm)+n 这个公式。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MOD = ; int main() {
int TCase;
cin >> TCase;
for(int t = ; t <= TCase; ++t) {
long long n, p, c;
long long ans = , flag = ;
cin >> n;
for(int i = ; i != n; ++i) {
long long tmp = , fac = ;
cin >> p >> c;
for(int j = ; j != c; ++j) {
fac = (fac * p) % MOD;
tmp = (tmp + fac) % MOD;
}
tmp = (tmp + (fac * c) % MOD) % MOD;
flag = (fac * flag) % MOD;
ans = (ans * tmp) % MOD;
}
ans = (ans + flag) % MOD;
cout << "Case " << t << ": " << ans << endl;
}
return ;
}
最新文章
- Alpha阶段项目Postmortem
- yii2.0 Cache缓存
- jenkins2 pipeline实例
- css编写的时候注意什么
- [Android Pro] android 混淆文件project.properties和proguard-project.txt
- CSS学习笔记之定位
- select into from 和 insert into select 的用法和区别
- Myeclipse安装破解
- LeetCode算法题-Shortest Completing Word(Java实现)
- [LeetCode] Lemonade Change 买柠檬找零
- 《JavaScript 高级程序设计》读书笔记一 简介
- Xcode - Xcode10上传应用到AppStore
- bootstrap3 input 验证样式【转】
- 电脑时间显示秒 win10电脑显示农历
- PHP系统级函数 get_headers() 包含有服务器响应一个 HTTP
- HDU 3078 LCA转RMQ
- POJ 1815 Friendship(最小割+字典序输出割点)
- 日志生成控制文件syslog.conf
- MySQL的数据引擎讲解
- SR领域文献资源汇总(链接地址)