电商网站代码设计,网站开发与应用专业就业方向,相应式网站,商城类网站怎么优化[hdu 7111] Brunhilda’s Birthday#xff09;
题意#xff1a;
和P6756 [BalticOI2013] Brunhilda’s Birthday#xff09;一样的 给你p个质数集#xff0c;您可以进行任意多次操作#xff0c;每一次操作时#xff0c;您选择一个素数pip_{i}pi,这会使得n-⌊npi⌋…[hdu 7111] Brunhilda’s Birthday
题意
和P6756 [BalticOI2013] Brunhilda’s Birthday一样的 给你p个质数集您可以进行任意多次操作每一次操作时您选择一个素数pip_{i}pi,这会使得n-⌊npi⌋∗pi\lfloor \frac{n}{p_{i}} \rfloor*p_{i}⌊pin⌋∗pi 现在给你一个n让你计算1到n所有数的操作到0的操作次数记a[i]:表示将i操作为0的最小操作次数 输出∑1≤n≤Nan∗23333N−nmod264\sum_{1\le n\le N}a_{n}*23333^{N-n}\mod 2^{64}∑1≤n≤Nan∗23333N−nmod264
Sample Input
1
6 2
2
3Sample Output
17181031198765592570HintIn the sample case, ai is {1,1,2,3,3,0}. 题解
通过这个样例再加上自己手写例子不难发现
如果i大于所有质数的乘积答案一定是0也就是边界值是质数集的乘积小于他有解否则无解如果有解ai是非递减序列而且是区间呈现的每个值都覆盖一段区间
证明我不是很清楚。。。只是手推出的性质 详细证明可以看这个 既然是非严格单调递增那我们就可以试着贪心去找答案 对于一个数x我们想让其尽快减到0肯定要选一个p满足x mod p最大这样x-(x mod p)才会更小。那么我们反着想什么样的数转移到x最优区间[x1,x-1(x mod p)]转至x时最优然后我们循环每个p去找这个区间更远的右端点这样可以让更多的点操作少 复杂度: 最后复杂度大概是一个O(|P|log n),|P|是是指质数集大小
代码
// Problem: Remove
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/showproblem.php?pid7111
// Memory Limit: 262 MB
// Time Limit: 6000 ms
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug( a, b ) printf ( %s %d\n, a, b );
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
// Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read (){};
template typename _Tp, typename... _Tps void read ( _Tp x, _Tps ...Ar )
{x 0;char c getchar ();bool flag 0;while ( c 0 || c 9 )flag | ( c - ), c getchar ();while ( c 0 c 9 )x ( x 3 ) ( x 1 ) ( c ^ 48 ), c getchar ();if ( flag )x -x;read ( Ar... );
}
template typename T inline void write ( T x )
{if ( x 0 ){x ~( x - 1 );putchar ( - );}if ( x 9 )write ( x / 10 );putchar ( x % 10 0 );
}
void rd_test ()
{
#ifdef LOCALstartTime clock ();freopen ( in.txt, r, stdin );
#endif
}
void Time_test ()
{
#ifdef LOCALendTime clock ();printf ( \nRun Time:%lfs\n,(double)( endTime - startTime ) / CLOCKS_PER_SEC );
#endif
}
#define int ull
const int maxn 2e6 9;
int prime[maxn];
ull ans[maxn];
ull poww ( ull a, ull b )
{ull ans 1;while ( b ){if ( b 1 )ans ans * a;a a * a;b 1;}return ans;
}
signed main ()
{// rd_test();int t;read ( t );while ( t-- ){int n, p;read ( n, p );int maxx 0;for ( int i 1; i n; i )ans[i] 0;for ( int i 1; i p; i )prime[i] 0;for ( int i 1; i p; i ){read ( prime[i] );maxx max ( maxx, prime[i] );}for ( int i 1; i min ( maxx, n ); i ){ans[i] 1;}int r 0;for ( int i maxx - 1; i n; i r ){r 0;for ( int j 1; j p; j ){r max ( r, i / prime[j] * prime[j] prime[j] - 1 );}// cout r r endl;for ( int j i 1; j r; j )ans[j] ans[i] 1;if ( i r )break;}ull sum 0;// for ( int i 1; i n; i )// {// cout ans ans[i] endl;// }ull fac 1;for ( int i n; i 1; i-- ){sum ans[i] * fac;fac fac * 23333;}cout sum endl;}// Time_test();
}
