模拟赛41 A. 四个质数的和
2024-09-06 10:45:32
题目描述
给定了一个正整数 \(N\)。有多少种方法将 \(N\) 分解成为四个质数 \(a,b,c,d\)的和。
例如:
\(9=2+2+2+3=2+2+3+2=2+3+2+2=3+2+2+2\),故共有 \(4\) 种方法将 \(9\) 分解成为四个整数。
输入格式
本题多组数据测试:
第一行读入一个整数 \(T\) 表示数据组数。
接下来共 \(T\) 行,每行包含一个正整数 \(N\)。
输出格式
共 \(T\) 行,每行一个整数表示答案。
样例
样例输入
2
9
10
样例输出
4
6
数据范围与提示
对于 \(10\%\) 的数据,\(N \leq 10\)。
对于 \(40\%\) 的数据,\(N \leq 100\)。
对于 \(70\%\) 的数据,\(N \leq 1000\)。
对于 \(1000\%\) 的数据,\(T \leq 10,N \leq 100000\)。
分析
可以设 \(f[i][j]\) 为当前用了 \(j\) 个质数拼出 \(i\) 的方案数
状态数太多转移不动
可以改为先求出两两质数的和,再用这个和去拼出想要的数
代码
#include<cstdio>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
int t,n,pri[maxn];
bool not_pri[maxn];
long long f[maxn][4];
void pre(int now){
not_pri[0]=not_pri[1]=1;
for(rg int i=2;i<=now;i++){
if(!not_pri[i]) pri[++pri[0]]=i;
for(rg int j=1;j<=pri[0] && 1LL*i*pri[j]<=now;j++){
not_pri[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
for(rg int i=1;i<=pri[0];i++){
f[pri[i]][1]=1;
}
for(rg int o=2;o<=2;o++){
for(rg int i=1;i<=now;i++){
if(f[i][o-1]){
for(rg int j=1;j<=pri[0];j++){
if(i+pri[j]<=now){
f[i+pri[j]][o]+=f[i][o-1];
} else {
break;
}
}
}
}
}
}
long long ans;
int main(){
t=read();
pre(100000);
while(t--){
n=read();
ans=0;
for(rg int i=2;i<=n;i++){
ans+=f[i][2]*f[n-i][2];
}
printf("%lld\n",ans);
}
return 0;
}
最新文章
- 怎么样修改PHPStorm中文件修改后标签和文件名的颜色与背景色
- JFinal Db + Record模式 - ORM 框架
- C,C++经典(程序、错误程序)
- [译]Stairway to Integration Services Level 12 - 高级日志配置
- Golang爬虫示例包系列教程(一):pedaily.com投资界爬虫
- 编写PHP代码总结
- TCP/IP笔记(六)TCP与UDP
- 跨语言时区处理与Epoch
- ps中如何让图层在画布内水平居中
- 带着新人看java虚拟机07(多线程篇)
- [Swift]LeetCode166. 分数到小数 | Fraction to Recurring Decimal
- asp.net core 系列 4 注入服务的生存期
- varnish学习以及CDN的原理
- python-GIL、死锁递归锁及线程补充
- MySQL 性能监控4大指标——第一部分
- json数据在前端(javascript)和后端(php)转换
- &#39;java&#39; 不是内部或外部命令,也不是可运行的程序的两个解决办法
- win10 计算器calc命令打不开
- MapServer:地图发布工具
- 微信开发之c#下获取jssdk的access_token
热门文章
- gulp 打包安装
- 云计算管理平台之OpenStack网络服务neutron
- Github优质库分享-01算法小抄 基于LeetCode
- 测试可变字符序列stringBuilder
- 1,web项目工作流程
- git 出现 error: bad signature fatal: index file corrupt
- SPOJ16607 IE1 - Sweets
- 仅用六种字符来完成Hello World,你能做到吗?
- Java_数组, 懒得整理了 --------------------->; 未完, 待续
- 【SpringCloud】01.常见软件架构的区别