首页 > 其他分享 >hdu 2608 0 or 1(数论)

hdu 2608 0 or 1(数论)

时间:2023-02-24 10:33:53浏览次数:53  
标签:hdu ei 数论 2608 pm 因子 +...+ e1 e2


0 or 1

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1659    Accepted Submission(s): 418


Problem Description


Solving problem is a interesting thing. Yifenfei like to slove different problem,because he think it is a way let him more intelligent. But as we know,yifenfei is weak in math. When he come up against a difficult math problem, he always try to get a hand. Now the problem is coming! Let we
define T(n) as the sum of all numbers which are positive integers can divied n. and S(n) = T(1) + T(2) + T(3)…..+T(n).

 


Input


The first line of the input contains an integer T which means the number of test cases. Then T lines follow, each line consists of only one positive integers n. You may assume the integer will not exceed 2^31.


 

Output


For each test case, you should output one lines of one integer S(n) %2. So you may see the answer is always 0 or 1 .


 


 


Sample Input


3
1
2
3


 


 


Sample Output


Hint

Hint S(3) = T(1) + T(2) +T(3) = 1 + (1+2) + (1+3) = 8
S(3) % 2 = 0


 


Author


yifenfei

 


Source


​奋斗的年代 ​


 


 


Recommend


yifenfei


 

思路:

对于每一个数N,我们可以将其拆分为  N= p1^e1 * p2^e2 * p3^e3 * ...  * pm^em. 其中p1,p2...都是质因子,这可以回想到我们求两数的最大公约数时,我们就是将一个数拆分成质因子相乘的形式。那么首先提出一个问题,那就是数N有多少个因子了,知道排列组合的话,很快就能知道,这个结果是 K=( e1+1 )* ( e2+1 )* ... *( em+1 )因为每个质因子 pi 我们都可以取 0-ei 个来组合成一个因子,当每个都取零时,这个因子就是 1 ,当每个都去最大值时,这个因子就是 N 本身,那么如何得到这 K 个因子的和呢?我们补全 N 的质因子乘积形式,将所有质因子补全,N= 2^e1 * 3^e2 * 5^e3 * 7^e4 * 11^ e5 *......   T[N]= [ ( 2^0+2^1+...+2^e1 )*( 3^1+3^2+...+3^e2 )*...*( pm^0+pm^1+...+pm^em ) ]% 2;   我们知道 ( 2^0+2^1+...+2^e1 )% 2= 1 恒成立(因为有2^0=1),所以T[N]的值只取决与后面的乘式%2 是否出现了0,那么后面的式子怎样才会是零呢?很简单,因为所有的质素都是奇数,所以当除2以外的存在某一个质因子表达式为偶数项的时候就会为零了,也即只要满足至少存在一个 ei 的值为奇数(项数为ei- 0+ 1)。当然这题中,我们不会去直接计算为0的T[]有多少多,这很困难,而是从反面求解,即计算T[]为1的数的个数,这样,求S[N]也就转化为从1-N有多少个T[i]为1。回到前面,如果T[i]为1,那么除 2 之外所有质因子的 ei 都为偶数,这个条件就很好解决了,而不像前面的求解满足至少一项 ei 为奇数,既然除2之外所有的 ei 都为偶数,那么这个数一定会是 i= x^2 或者是 i= 2* x^2的形式。所以统计从 1-N 之间有多少个满足T[i]= 1数吧。

 

#include<iostream>
using namespace std;
int main()
{
int cas;
while(cin>>cas)
{ long long sum,ans=0;
while(cas--)
{ cin>>sum;ans=0;
for(long long i=1;i*i<=sum;i++)
{ ++ans;
if(2*i*i<=sum)++ans;
}
ans%=2;
cout<<ans<<"\n";
}
}
}

 

 

 

标签:hdu,ei,数论,2608,pm,因子,+...+,e1,e2
From: https://blog.51cto.com/u_15953788/6082906

相关文章

  • HDU 2888 Check Corners (二维RMQ,3级)
    A-CheckCornersCrawlinginprocess...CrawlingfailedTimeLimit:10000MS    MemoryLimit:32768KB    64bitIOFormat:%I64d&%I64u​​Submit......
  • Codeforces - 1244C - The Football Season(暴力 + 数学规律 + 数论 / *2000)
    1244C-TheFootballSeason(⇔源地址)目录1244C-TheFootballSeason(⇔源地址)tag题意思路暴力解(枚举)数论解(扩展欧几里得)AC代码错误次数:2tag⇔......
  • HDUOJ 2000-2100
    2024C语言合法标识符ProblemDescription输入一个字符串,判断其是否是C的合法标识符。 Input输入数据包含多个测试实例,数据的第一行是一个整数n,表示测试实例的个数,然......
  • [hdu 5307] He is Flying (FFT)
    题意给出长度为的数列,对于任意,求出区间和为的区间的长度之和题目分析有了几道fft题的经验,套路就是把可加性的计算化为幂的次数做多项式卷积有分别把看成两个多项式,做FF......
  • [bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)
    题面设为的约数个数,给定,求题目分析有这样一个结论这道题就是下面这道题的数据增强版,那么这个结论的证明就不再赘述,请自行查看下面的(蒟蒻)博客​​传送门:[SDOI2015][bz......
  • [HDU 5608]Function(莫比乌斯反演 + 杜教筛)
    题目描述有求只有最多组数据题目分析如此一来就可以杜教筛了,然而仅仅这样还是会T,于是我们在想一想如何筛出前面一部分的值令,根据莫比乌斯反演于是用筛出前项就行了......
  • HDU 1238 Substrings
    SubstringsTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):7699    AcceptedSubmission(s):3474......
  • HDU 1256 画8
    画8TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):4645    AcceptedSubmission(s):2004Proble......
  • HDU 1219 AC Me
    ACMeTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):13482    AcceptedSubmission(s):5934Pro......
  • 密码学简单数论(3):算术基本定理证明、等价关系、同余和乘法逆元
    参考资料:1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c算术基本定理证明  定理2-2(算术基本定......