Yes, full reformat and you lose all your data, quick, but will not fix problems. It doesn't delete other files, just adds the ones that are essential, and that you probably already have.
Please visit
this website and you will find some tools there. It detects duplicate files and you can delete them manually or using another tool.
Now, it may fix the problem, but I am afraid there is possinility you have a virus.
But it's just a possibility. Please try the solution above and tell for the result.