今天现场赛模拟来着,D题做的很快,15分钟就出了,然后就一直死磕I题了,刚开始想到了要减去不互素的数,结果不知道容斥原理,只能赛后AC了。
大体思路就是,先算出1到n的四次方和,然后减去不互素的四次方和,然后计算这个就比较麻烦了,首先把n给素数分解,然后就运用容斥原理,各种减减加加,目的就是防止减掉重复的,比如2的倍数有2,4,6,8……,3的倍数有3,6,9……,然后2和3中都有6,所以这点就比较麻烦了。类似的还有含多个质因子的数。
然后我容斥是用dfs实现的,其中也有好多细节吧,比如计算四次方和公式里面,有个除以30,就不能用模了,但是,不用又会超,听别人说用逆元做的,我也不知道是啥,就用了个很土的方法做的。然后乘法的时候每次乘都要模一次,减法的时候还可能出现负数,也要处理一下,总之,各种模了。
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 1005
#define INF 100000000
#define eps 1e-7
using namespace std;
struct wwj
{
int num;
int cnt;
}node[200];
bool tag[120001];
long long p[110001], v[200];
int cnt, num;
long long n, m;
long long mod = 1000000007LL;
long long f(long long x)
{
long long x1 = x;
long long x2 = (x + 1);
long long x3 = (2 * x + 1);
long long x4 = (3 * x * x + (3 * x - 1));
if(x1 % 2 == 0) x1 /= 2;
else if(x2 % 2 == 0) x2 /= 2;
else if(x3 % 2 == 0) x3 /= 2;
else if(x4 % 2 == 0) x4 /= 2;
if(x1 % 3 == 0) x1 /= 3;
else if(x2 % 3 == 0) x2 /= 3;
else if(x3 % 3 == 0) x3 /= 3;
else if(x4 % 3 == 0) x4 /= 3;
if(x1 % 5 == 0) x1 /= 5;
else if(x2 % 5 == 0) x2 /= 5;
else if(x3 % 5 == 0) x3 /= 5;
else if(x4 % 5 == 0) x4 /= 5;
x4 %= mod;
return x1 * x2 % mod * x3 % mod * x4 % mod;
}
void get_prime()
{
cnt = 0;
for (int i = 2; i < 11000; i++)
{
if (!tag[i])
p[cnt++] = (long long)i;
for (int j = 0; j < cnt && p[j] * i < 11000; j++)
{
tag[i * p[j]] = 1;
if (i % p[j] == 0)
break;
}
}
}
long long sum;
void dfs(int x, int ct, int deep)
{
if(ct >= deep ) return;
v[ct] = node[x].num;
if(ct == deep - 1)
{
long long xx = v[0];
for(int j = 1; j <= ct; j++)
xx *= v[j];
sum = (sum + f(m / xx) * xx % mod * xx % mod * xx % mod * xx % mod) % mod;
return;
}
for(int i = x + 1; i < num; i++)
dfs(i, ct + 1, deep);
}
int main()
{
#ifdef LOCAL
freopen("d:/data.in","r",stdin);
freopen("d:/data.out","w",stdout);
#endif
int t, i, j;
get_prime();
long long ans;
cin >> t;
while(t--)
{
cin >> m;
n = m;
num = 0;
for(i = 0; i < cnt && p[i] * p[i] <= n; i++)
{
int tmp = 0;
if(n % p[i] == 0)
{
while(n % p[i] == 0)
{
tmp++;
n /= p[i];
}
node[num].num = p[i];
node[num++].cnt = tmp;
}
}
if(n != 1)
{
node[num].num = n;
node[num++].cnt = 1;
}
ans = f(m);
for(i = 1; i <= num; i++)
{
sum = 0;
long long tmp;
for(j = 0; j < num; j++)
dfs(j, 0, i);
tmp = sum;
if(i % 2)
ans = ((ans - tmp) % mod + mod) % mod;
else ans = (ans + tmp) % mod;
}
if(m == 1) puts("0");
else
cout << (ans + mod ) % mod << endl;
}
return 0;
}
分享到:
相关推荐
第36届ACM大赛北京赛区排名供准备参加这项赛事的学生参考
第34届ACM/ICPC亚洲区预选赛合肥赛区网络预选赛试题
ACM-ICPC 历年竞赛 真题,各大赛区真题详解,内含几大赛区各年度的真题
ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM...
2009acm年吉林赛区试题,觉得有点用,大家喜欢就可以
本资源是河南ACM省赛赛区第一届到第五届的题,可以帮助需要的人进行训练,了解出题的风格,并可以着手练习比赛的题目,提升动手编程的实力。
武汉工程大学第一届ACM程序设计竞赛试题 武汉工程大学第一届ACM程序设计竞赛试题 武汉工程大学第一届ACM程序设计竞赛试题 武汉工程大学第一届ACM程序设计竞赛试题 武汉工程大学第一届ACM程序设计竞赛试题
哈尔滨赛区竞赛题,喜欢ACM的同学必看,很有帮助。
2012ACM成都赛区现场赛原题,复旦大学命题,没去现场赛的同学可以学习一下。
ACM第一届ACM试题.pdf
第29届ACM国际大学生程序设计竞赛亚洲区北京赛区预选赛试题题解(一)
里面有山东省第一届ACM比赛试题及所有测试数据,输入需要从文件读取
12个ACM动态规划经典题 习题+分析+程序 (转载)
第33届ACM-ICPC亚洲区预赛(成都网络赛)题目 pdf格式
2008年六月一日,内蒙古赛区的ACM试题,一共十题,题目有中英文对照。感兴趣的可以做一做。
acm第100题 The 3n+1 problem #include <iostream> using namespace std; unsigned CyCle(unsigned m) { unsigned count = 1; while (m != 1) { if (m & 0x01) m = 3 * m + 1; else m = m / 2; ...
ACM大量习题题库 现在网上有许多题库,大多是可以在线评测,所以叫做Online Judge。除了USACO是为IOI准备外,其余几乎全 部是大学的ACM竞赛题库。 USACO http://ace.delos.com/usacogate 美国著名在线题库,专门为...
acm经典题库acm经典题库acm经典题库
2018年郑州轻工业学院第十届ACM程序设计大赛暨省内高校邀请赛颁奖仪式主持词.docx2018年郑州轻工业学院第十届ACM程序设计大赛暨省内高校邀请赛颁奖仪式主持词.docx2018年郑州轻工业学院第十届ACM程序设计大赛暨省内...