又是几天过去，最近在刷数论基础和dp基础。kuangbin数论专题刷了差不多一大半吧。深深感jio到自己的菜。唉，温故而知新，所以决定在踩一遍坑点。
bi-shoe and phi-shoe
https://vjudge.net/problem/lightoj-1370
题目大意：给出一些数字，对于每个数字找到一个欧拉函数值大于等于这个数的数，求找到的所有数的最小和。
分析：其实用欧拉筛打表欧拉函数值可以发现一个规律，质数的欧拉函数上升增加的速度远比其他数字快，所以此题只用找到第一个大于n的数即可。（别问我怎么证明的，，因为，，我也不知道0.0）
代码如下：
#include<bits/stdc++.h> using namespace std; const int n=1e7+5; bool prime[n]; void is_prime() { for(int i=2;i<n;i++) prime[i]=true; for(int i=2;i*i<n;i++) if(prime[i]) for(int j=i*i;j<=n;j+=i) prime[j]=false; } int main() { ios::sync_with_stdio(false); is_prime(); int t; cin>>t; for(int l=1;l<=t;l++) { int n; cin>>n; long long sum=0; for(int i=1;i<=n;i++) { int a; cin>>a; for(int j=a+1;j<n;j++) { if(prime[j]) { sum+=j; break; } } } cout<<"case "<<l<<": "<<sum<<" xukha"<<endl; } return 0; }
aladdin and the flying carpet
https://vjudge.net/problem/lightoj-1341
题目大意：给出一个长方形的面积a（不是正方形），给出该长方形最小的边b，问组成该面积的长方形有多少种组合方案。比如12 2,有{2,6}，{3,4}两种组合方案。
分析：求因子数一下就会想到唯一分解定理，然后这题就是求s的因数总个数然后减去小于b的情况。
代码如下：
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/603502.html